Non-overlapping Intervals
Remove the fewest intervals so none overlap — and see why sorting by end time is the only provably safe choice
Problem Statement
Given a list of intervals, return the minimum number to remove so that the rest do not overlap.
Input: [[1,2], [2,3], [3,4], [1,3]]
Output: 1
remove [1,3] and the rest fit
Input: [[1,2], [1,2], [1,2]]
Output: 2
keep one, remove the other two
Input: [[1,2], [2,3]]
Output: 0
touching does not count as overlapping hereIntuition
"Remove the fewest" is the same as "keep the most". That flip matters, because keeping is the question with a known greedy answer.
So: what is the largest set of intervals that do not overlap? Answer that, and the removals are total - kept.
Now the question is which interval to keep when two conflict. Three plausible rules:
| Rule | Fails on |
|---|---|
| Keep the one that starts earliest | [1,100] beats [2,3] and [4,5] — one long interval blocks two short ones |
| Keep the shortest | [1,5], [4,6], [5,9] — the short middle one blocks both neighbours |
| Keep the one that ends earliest | Nothing. This one is provably safe. |
The insight
When two intervals conflict, keep the one that finishes sooner.
Both occupy one slot in your answer, so keeping either costs the same. But the one ending earlier leaves more room for everything that follows. It is never worse, and often better.
Sort by end time and this becomes a single pass.
Why "earliest end" is provably safe
This is the part worth understanding — the rest is bookkeeping.
Take any optimal answer and look at its first interval. The greedy choice ends no later than it, because greedy picked the earliest-ending interval available.
Swap the greedy pick in. Everything that fit after the optimal first interval still fits, because the greedy one frees up at least as much space. The answer is still valid and still the same size.
Repeat for each position. Every optimal solution can be transformed into the greedy one without getting worse — so greedy is optimal too. That is the exchange argument, and it is what separates this from a guess.
Approach
Sort by end time
Not start. This is the entire trick, and it is the line people get wrong.
Track the end of the last interval you kept
Start it at negative infinity so the first interval always fits.
For each interval, keep it or remove it
Starts at or after the last kept end → no conflict. Keep it, and update the tracked end.
Starts before → it overlaps. Remove it, and count it. The tracked end does not change, because you kept the earlier-ending one.
Solution
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
"""Minimum intervals to remove so none overlap.
Sort by END time and keep greedily: the interval finishing
soonest leaves the most room for the rest.
"""
if not intervals:
return 0
intervals.sort(key=lambda interval: interval[1])
removed = 0
last_end = float("-inf")
for start, end in intervals:
if start >= last_end:
last_end = end # keep it
else:
removed += 1 # drop it; last_end is unchanged
return removedDo not update `last_end` when removing
On a conflict, the interval being removed is the one ending later — sorting guaranteed that. Setting last_end = end there would replace a good interval with a worse one and block later fits.
Leaving last_end alone is what makes the greedy choice stick.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1)
Time — the sort dominates; the pass is O(n).
Space — two variables beyond the sort's own overhead.
Edge Cases
Related Problems
- Merge Intervals — sorted by start instead, and merging rather than discarding
- Jump Game — another greedy whose safety needs an argument
- Greedy — the exchange argument in general