aloalgoNon-overlapping Intervals
Medium
You are given a collection of intervals.
Your task is to find the minimum number of intervals that must be removed so that the remaining intervals are non-overlapping.
Note that:
- For every
interval, its end point is always greater than its start point. - Two
intervals[a, b]and[c, d]are considered non-overlapping ifb <= cord <= a. For example,[1,2]and[2,3]are non-overlapping.
Return the minimum number of intervals to remove.
Example 1
Input
[ [1, 3], [3, 5] ]
Output
0
Explanation:
The intervals [1,3] and [3,5] do not overlap, so no intervals need to be removed.
Example 2
Input
[ [1, 3], [3, 5], [2, 4] ]
Output
1
Explanation:
The interval [2,4] overlaps with both [1,3] and [3,5]. Removing [2,4] leaves the non-overlapping intervals [1,3] and [3,5].
Example 3
Input
[ [1, 2], [1, 3] ]
Output
1
Explanation:
The intervals [1,2] and [1,3] overlap. Removing either one will leave a non-overlapping interval.
Input
[ [1, 3], [3, 5] ]
Output
0