Non-overlapping Intervals
Given an array of intervals where intervals[i] = [start, end], return the minimum number of intervals you need to remove to make the rest non-overlapping. Two intervals [a, b] and [c, d] overlap when c < b and a < d.
Click bars above to remove overlaps, and see the fewest removals it takes to leave no red pairs.
Input & Output
Input
intervals — an array of intervals where intervals[i] = [starti, endi]
Output
the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping
Example
Input
intervals = [[1,2],[2,3],[3,4],[1,3]]
Output
1
Explanation
[1,3] can be removed and the rest of the intervals are non-overlapping.
Example
Input
intervals = [[1,2],[1,2],[1,2]]
Output
2
Explanation
You need to remove two [1,2] intervals to make the rest of the intervals non-overlapping.
Example
Input
intervals = [[1,2],[2,3]]
Output
0
Explanation
You don't need to remove any of the intervals since they're already non-overlapping.
Constraints
- 1 <= intervals.length <= 10^5
- intervals[i].length == 2
- -5 * 10^4 <= starti < endi <= 5 * 10^4