Fewest Intervals to Remove
You get a list intervals. Each item is a pair [start, end] with start < end. The list is not sorted.
Remove some intervals so that no two of the remaining intervals overlap. Return the smallest number of intervals you must remove.
What counts as overlap
- Two intervals overlap when they share more than one point. For example,
[2, 6]and[4, 9]overlap. - Two intervals that only touch at an end point, such as
[2, 5]and[5, 8], do not overlap. You can keep both. - Two equal intervals overlap.
Hint: removing as few as possible is the same as keeping as many as possible. Think about which interval you should keep first: the one that leaves the most room for the others.
Examples
Example 1
- Input:
- [[1,4],[3,6],[6,9],[2,3],[4,7]]
- Output:
- 2
Keep [2, 3], [3, 6] and [6, 9]. They only touch at 3 and 6, so they do not overlap. Remove [1, 4] and [4, 7]. You can not keep 4 intervals, so 2 is the smallest number to remove.
Example 2
- Input:
- [[0,20],[1,2],[3,4],[5,6]]
- Output:
- 1
[0, 20] overlaps all three short intervals. Remove only [0, 20], and the three short intervals stay.
Example 3
- Input:
- [[5,8],[5,8],[5,8]]
- Output:
- 2
All three intervals are the same, so any two of them overlap. Only one can stay.
Constraints
1 <= intervals.length <= 140 <= start < end <= 60
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.