Sweaty Imposter

Non-overlapping Intervals

MediumMerge IntervalsBlind 75MidOpen on LeetCodeUpdated

You're given an array intervals where intervals[i] = [start_i, end_i]. Return the minimum number of intervals you need to remove so that none of the remaining intervals overlap each other. Intervals that only touch at an endpoint, like [1,2] and [2,3], do not count as overlapping. The input is not sorted, and you return only the count, not which intervals to remove.

Examples

intervals = [[1,2],[2,3],[3,4],[1,3]] returns 1

[1,2][2,3][3,4][1,3]1234
Removing the highlighted [1,3] is enough.

[1,3] overlaps both [1,2] and [2,3]. Removing just [1,3] leaves [1,2], [2,3] and [3,4], which only touch at endpoints.

intervals = [[1,2],[1,2],[1,2]] returns 2

All three intervals are identical, so any two of them overlap. You can keep only one and must remove the other two.

intervals = [[1,2],[2,3]] returns 0

The intervals share only the point 2, which is not an overlap, so nothing needs to go.

Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= start_i < end_i <= 5 * 10^4

Hints

Hint 1

Removing the fewest intervals is the same as keeping the most. If you had to keep one interval first, which would leave the most room for the rest?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Removing the fewest is the same as keeping the most. Sort by end time and scan, keeping an interval when its start is at or after the end of the last kept one and counting it as removed otherwise. The interval that finishes first leaves the most room for everything after it, so keeping it is never worse. The sort dominates; the scan itself uses O(1) extra space.

Time

O(n log n)

Space

O(n)

Pitfall

Sorting by start instead of end breaks the simple greedy: a long early interval like [1,100] gets kept and blocks everything after it. Touching is allowed, so keep an interval when start >= lastEnd, not start > lastEnd.

Solutions

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