Non-overlapping Intervals
Non-overlapping Intervals is a medium Intervals problem from the Blind 75. The key pattern is greedy by end, and a good solution runs in O(n log n) time.
Problem
Return the minimum number of intervals to remove so the remaining intervals do not overlap.
Examples
Example 1
Input
[[1,3],[2,4],[4,6],[5,7]]Output
2Example 2
Input
[[3,4],[3,4],[3,4]]Output
2Example 3
Input
[[1,50],[5,10],[10,20],[2,6]]Output
2Approach
Sort by end time and keep each interval that starts at or after the last kept end. Everything else is removed.
| Pattern | Greedy by end |
|---|---|
| Time | O(n log n) |
| Space | O(1) beyond sorting |
Watch out for
Intervals that only touch at an endpoint do not overlap.