Non-overlapping Intervals
MediumIntervals
You are given an array of intervals intervals, where intervals[i] = [start, end] and start < end. The intervals are not in any particular order.
Return the minimum number of intervals you must remove so that none of the remaining intervals overlap each other.
Two intervals overlap only if they share more than an endpoint: [1, 3] and [2, 4] overlap, but [1, 2] and [2, 3] do not, because one ends exactly where the other begins. Identical intervals overlap.
Example 1
- Input:
- intervals = [[1, 3], [2, 4], [3, 5], [1, 10]]
- Output:
- 2
- Explanation
- Keep
[1, 3]and[3, 5], which only touch at 3.[2, 4]overlaps both and[1, 10]overlaps everything, so those 2 are removed.
Example 2
- Input:
- intervals = [[4, 6], [1, 2], [2, 4]]
- Output:
- 0
- Explanation
- In order they are
[1, 2],[2, 4],[4, 6]. Each one starts exactly where the previous ends, which does not count as overlapping, so nothing is removed.
Example 3
- Input:
- intervals = [[-3, 1], [-3, 1], [0, 2]]
- Output:
- 2
- Explanation
- The two copies of
[-3, 1]overlap each other and both overlap[0, 2], so only one interval can stay and 2 are removed.
Constraints
1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= start < end <= 5 * 10^4