Non-overlapping Intervals – Solution & Complexity
Solution Walkthrough
1. Understand the Goal
- Find the minimum number of intervals to delete so that none of the survivors overlap — equivalently, find the MAXIMUM number of mutually non-overlapping intervals you can keep, then subtract that count from the total.
- Intervals that only touch at an endpoint (like
[1,2]and[2,3]) count as non-overlapping and may both survive.
2. Choose the Core Pattern
- This is "activity selection": sort by end time and greedily keep the interval that finishes earliest whenever a conflict is found.
- The exchange argument: among any set of intervals that overlap, whichever one ends earliest leaves the most room for everything after it — swapping any other choice for the earliest-ending one can never make the remaining selection worse, so the greedy choice is always at least as good as any alternative.
3. Build the Algorithm
- Sort all intervals by end time ascending.
- Track
lastEnd, the end time of the most recently kept interval, starting at negative infinity (or the first interval's end after keeping it). - Scan left to right: if the current interval's start is >=
lastEnd, it doesn't overlap the last kept interval — keep it and updatelastEndto its end. Otherwise it overlaps, so it must be removed; do not updatelastEnd(the interval already kept still ends earlier, so it stays the better anchor). - The answer is
total intervals - kept count.
4. Check Edge Cases
- 0 or 1 intervals: nothing can overlap, so 0 removals.
- All intervals identical or fully nested: only the true earliest-ending interval survives per overlapping cluster; every other overlapping one gets removed.
- Intervals that only touch at endpoints (
[1,2],[2,3]): the>=comparison (not>) on start vs.lastEndmust treat these as non-overlapping, or the count will be wrong.
5. Final Solution and Complexity
- Time complexity is O(n log n).
- Space complexity is O(1) beyond the sort output model.
