The problem
Return the fewest intervals to remove so that the rest do not overlap. Intervals that only touch, like [1, 2] and [2, 3], do not overlap.
Examples
01
- Input
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
- Output
1
02
- Input
intervals = [[1, 2], [1, 2], [1, 2]]
- Output
2
03
- Input
intervals = [[1, 2], [2, 3]]
- Output
0
Constraints
- 1 ≤ intervals.length ≤ 10⁵
- −5 × 10⁴ ≤ start < end ≤ 5 × 10⁴
The idea
Removing the fewest is keeping the most. Sort by end and keep greedily: take the interval that ends first, then the next that starts after it ends, and so on.
Why the earliest end: whatever the best selection’s first interval is, swapping it for the one that ends first cannot cause a clash — it ends even sooner — so there is always a best selection that starts that way. The same argument repeats for every later choice. The answer is the number not kept.
- Time
- O(n log n)
- Space
- O(1) besides the sort
Solution · every language run against every case
class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: # Keep as many as possible: always keep the one that ends first — it leaves the most room. intervals.sort(key=lambda iv: iv[1]) kept, end = 0, float("-inf") for s, e in intervals: if s >= end: # fits after the last one kept (touching is fine) kept, end = kept + 1, e return len(intervals) - kept