You are given a list of ranges intervals, each [start, end] with start < end. Return the
smallest number of ranges you must remove so that no two of the remaining ranges overlap.
Here, ranges that only touch at an end point do not overlap: [1, 3] and [3, 5] can both
stay.
Example 1
- Input
- intervals = [[1, 4], [2, 3], [3, 6], [5, 7]]
- Output
- 2
[1, 4] and [5, 7]. [2, 3] and [3, 6] only touch, so both can stay.Example 2
- Input
- intervals = [[0, 5], [0, 5], [0, 5]]
- Output
- 2
Constraints
intervalsholds 1 to 10⁵ ranges.- −5 × 10⁴ ≤
start<end≤ 5 × 10⁴
Show the pattern
Intervals, Greedy
Keeping the most ranges is the classic scheduling choice: sort by end and always keep the range that finishes first, since it leaves the most room for the rest. Whatever you don't keep, you remove.
See intervals in a visualiserShow the approach
Removing the fewest ranges means keeping as many as possible that don't overlap. Sort the ranges by end. Keep the first; then for each next range, if it starts at or after the end of the last kept range (touching is allowed), keep it and remember its end. Otherwise it clashes, so count it as removed.
Why the earliest end is safe: the range that finishes first leaves the most room after it, so putting it in place of the first range of any best selection never causes a clash.
Time: O(n log n) · Space: O(n) for the sorted copy