Fewest removals to avoid overlap
We'll cover the following
Remove the fewest intervals so that none of the remaining ones overlap.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
1-40
2-51
3-72
5-83
6-94
8-115
9-136
10-147
12-158
13-179
15-1910
16-2011
18-2212
21-2513
Sorted by end time for you. Greedy rule: always keep the interval that ends earliest, since it leaves the most room for the rest.
1 / 16
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n log n) | O(1) | Sort by end, then one greedy pass. |
In Python
def erase_overlap(intervals):
intervals.sort(key=lambda x: x[1])
end, removed = float('-inf'), 0
for s, e in intervals:
if s >= end: end = e
else: removed += 1
return removedSummary: say it in the interview
- Sort by end time and keep an interval whenever it starts after the last kept one ends. Finishing early leaves the most room for later intervals, so this greedy choice is always safe.
- Time O(n log n), space O(1). Sort by end, then one greedy pass.