Non-overlapping Intervals

MediumArray Greedy Sorting Intervals

A single meeting room received overlapping booking requests, each given as intervals[i] = [start, end] with start < end. The office manager wants to cancel as few bookings as possible so that none of the remaining bookings overlap.

Return the minimum number of bookings to cancel. A booking that ends at the exact moment another one starts, such as [9,10] and [10,11], does not overlap with it.

Example 1

Input: intervals = [[1,4],[3,6],[6,9],[2,3]]
Output: 1

Explanation: Cancelling [1,4] leaves [2,3], [3,6] and [6,9], which only touch.

Example 2

Input: intervals = [[1,5],[2,6],[3,7],[6,8]]
Output: 2

Explanation: Keep [1,5] and [6,8]. The two bookings in between both overlap [1,5], and they overlap each other too.

Example 3

Input: intervals = [[7,8],[5,7]]
Output: 0

Explanation: The two bookings only touch at 7, so nothing has to be cancelled.

Constraints

There are between 1 and 10^5 bookings.
Start and end times are integers from -50,000 to 50,000, and every booking starts strictly before it ends.

Follow-up: Why does sorting by start (and keeping the earliest-starting interval) fail? Find a small counterexample.

💡 Hint 1

Deleting as few as possible is the same as keeping as many non-overlapping intervals as possible.

💡 Hint 2

Among intervals that could come next, which one leaves the most room for the rest? The one that ends earliest.

💡 Hint 3

Sort by end. Keep an interval whenever its start is at or after the end of the last kept one; otherwise it has to go.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Flip the question: find the largest set of intervals that do not overlap, and delete the rest. The classic greedy is to sort by end and always keep the interval that finishes first. It leaves the most room for everything after it, so an exchange argument shows it is never worse than any other choice. Walk the sorted list with lastEnd: if start >= lastEnd, keep the interval and set lastEnd = end; otherwise count a deletion.

Time O(n log n)Space O(n) for the sorted copy

function eraseOverlapIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let removed = 0;
  let lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) lastEnd = end;
    else removed++;
  }
  return removed;
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1]));
        int removed = 0;
        long lastEnd = Long.MIN_VALUE;
        for (int[] iv : sorted) {
            if (iv[0] >= lastEnd) lastEnd = iv[1];
            else removed++;
        }
        return removed;
    }
}

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function eraseOverlapIntervals(intervals) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit