61. Non-overlapping Intervals

You are given an array of intervals intervals, where intervals[i] = [start, end] and start < end.

Return the minimum number of intervals to delete so that no two of the remaining intervals overlap.

Two intervals that only share an endpoint, such as [1,2] and [2,3], do not overlap.

Example 1

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

Explanation: Delete [2,4]; [1,3] and [3,5] only touch.

Example 2

Input: intervals = [[1,5],[1,5],[1,5]]
Output: 2

Explanation: Identical intervals overlap, so only one copy can stay.

Example 3

Input: intervals = [[1,2],[2,3]]
Output: 0

Constraints

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= start < end <= 5 * 10^4

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