Non-overlapping Intervals
Given a list of half-open intervals, return the minimum number you must remove so that the remaining intervals do not overlap. Intervals that merely touch at an endpoint do not overlap.
- 1 ≤ intervals.length ≤ 10^5
- -5 · 10^4 ≤ start < end ≤ 5 · 10^4
- Minimum removals = n − maximum set of compatible intervals
- Classic activity selection: sort by end time
- Keep the interval that finishes earliest
Sort by start (or end) time and sweep: two intervals overlap iff the next start is before the current end, and after sorting each interval only needs comparing with the one being built. Counting concurrent intervals is a sweep over sorted endpoints, or a min-heap of end times.
Sort intervals by end. Greedily keep an interval whenever its start is at least the end of the last kept interval, and count it; otherwise it overlaps and is removed. Keeping the earliest-ending interval leaves the most room for the rest, which is the exchange argument behind activity selection. The answer is n - kept.
- Sorting by start and always dropping the interval with the larger end when two overlap is an equivalent greedy. DP over sorted intervals is O(n^2) and unnecessary.