Non-overlapping Intervals
Return the minimum number of intervals to remove so that the rest are non-overlapping.
- 1 <= intervals.length <= 10⁵
- intervals[i].length == 2
- -5 * 10⁴ <= starti < endi <= 5 * 10⁴
Intuition
Non overlapping intervals finds the fewest intervals to remove so none of the rest overlap. Removing the minimum is the same as keeping the maximum, which is the classic activity-selection problem.
That reframing decides the sorting key:
- Sort by end time, and greedily keep every interval that starts at or after the last kept interval's end.
The argument is that among competing intervals, the one ending earliest leaves the most room for everything after it. So keeping it is never worse than keeping any alternative, which makes the greedy optimal.
Sorting by start time is the classic error. A single long interval starting early would then be kept, blocking several short ones that together would have been better.
Walk the sorted list tracking the end of the last kept interval. If the next interval starts at or after that end, keep it and update; otherwise it overlaps and is counted as removed.
The comparison must be >=, since intervals that merely touch — [1, 2] and [2, 3] — do not overlap for this problem. Using > would wrongly remove one of them.
Counting removals directly is simpler than counting kept intervals and subtracting, though both work.
The greedy never needs to reconsider a kept interval, because sorting by end guarantees each choice is at least as good as any alternative at that point.
Sorting dominates at O(n log n), with the scan itself O(n) and O(1) extra space.
Classic activity selection: sort by end time and keep every interval that starts after the last kept one ends. Ending earliest leaves the most room for what follows, which is the exchange argument that makes this greedy optimal.
Approach
Before reading on: price up what the direct approach costs here, then ask what sorting by one endpoint makes obvious that was hidden before. Aim for O(n log n) time and O(1) space.
Reframe as keeping the maximum
Removing the fewest intervals is the same as keeping the most non-overlapping ones — the classic activity-selection problem.
Sort by end time
Sorting by end is what makes the greedy optimal. The earliest-ending interval leaves the most room for everything after it.
Avoid sorting by start
Sorting by start is the classic error. A single long early interval would be kept, blocking several short ones that were collectively better.
Track the last kept end
Walk the sorted list holding the end of the most recently kept interval. Each new interval is compared against just that value.
Keep or count as removed
If the next interval starts at or after the tracked end, keep it and update. Otherwise it overlaps and increments the removal count.
Treat touching as non-overlapping
Use >= — [1, 2] and [2, 3] merely touch and do not overlap, so strict comparison would wrongly remove one.
Cost of the approach
Sorting dominates at O(n log n) time, with the greedy scan O(n) and O(1) extra space.
Solution & live demo
Common pitfalls
Sorting by start time
intervals.sort(key=lambda x: x[0])
intervals.sort(key=lambda x: x[1])
A long interval starting early blocks everything behind it. Sorting by end time means each kept interval frees the maximum remaining space, which is exactly what maximises the count kept.
Treating touching intervals as overlapping
if s > lastEnd:
if s >= lastEnd:
[1,2] and [2,3] share only an endpoint and can both be kept. The strict test removes one unnecessarily and reports a higher removal count than needed.
Updating lastEnd when dropping an interval
else:
removed += 1
lastEnd = eelse:
removed += 1A removed interval isn't in the schedule, so it can't constrain what comes next — and since the list is sorted by end, its end is no earlier than the one already kept. Updating would only make the frontier worse.
Edge cases
Every interval is kept and 0 is returned.
One is kept and the remaining n - 1 are removed.
Not an overlap under this problem's definition, so the >= comparison keeps both.
Nothing to remove; the answer is 0.