You are given intervals, a list of n half-open intervals where intervals[i] = [start_i, end_i) covers every point from start_i up to but not including end_i. Implement min_intervals_to_remove(intervals) to find the smallest number of intervals that must be deleted so that no two of the intervals left over overlap.
Because the intervals are half-open, two intervals that merely touch at an endpoint do not overlap. For instance, [1, 2) and [2, 3) can both be kept, since the first finishes exactly where the second begins.
Example 1:
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: deleting [1, 3) leaves [1, 2), [2, 3) and [3, 4), which only touch at their endpoints, so a single removal suffices.
Example 2:
Input: intervals = [[1, 3], [2, 3], [3, 5]]
Output: 1
Explanation: [1, 3) and [2, 3) overlap, while [3, 5) only touches both of them at point 3. Removing either [1, 3) or [2, 3) leaves a non-overlapping set, so one deletion is enough.
intervals = [[1,1
| 0 | 1 | |
|---|---|---|
| 0 | 1 | 3 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
We have three intervals: [1,3], [2,3], and [3,5].
Example 3:
Input: intervals = [[2, 4], [2, 4], [2, 4]]
Output: 2
Explanation: All three intervals are identical and overlap one another, so only one of them can stay and two must be removed.
Example 4:
Input: intervals = [[1, 2], [3, 4], [5, 6]]
Output: 0
Explanation: No two intervals overlap, so nothing needs to be removed.
Constraints:
intervals = [[1,1
| 0 | 1 | |
|---|---|---|
| 0 | 1 | 3 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
We have three intervals: [1,3], [2,3], and [3,5].