Non-overlapping Intervals
Given intervals [start, end], return the minimum number of intervals to remove to make the rest non-overlapping.
Intervals that only touch at an endpoint (e.g. [1, 2] and [2, 3]) do not overlap.
Input: intervals is a list of [start, end] pairs (the example shows them as start:end comma-separated). Return the count as an integer.
Example
1:2,2:3,3:4,1:3
1
- The input
1:2,2:3,3:4,1:3is four intervals: , , and . Two intervals overlap only if they share more than a single point, so and , which just touch at , are compatible. - Check every pair: overlaps on the stretch from to , and overlaps on the stretch from to . Every other pair either touches at one endpoint or is disjoint.
- So the answer cannot be : the intervals as given contain two conflicts, and both involve .
- Removing leaves , , , which sit end to end with no overlap. Removing any other single interval leaves at least one conflict with in place.
- The minimum is therefore
1. Notice that this is the same as : the total count minus the size of the largest set of intervals that can all be kept together.
Constraints
- 1 <= len(intervals) <= 10^5
- -5 * 10^4 <= start < end <= 5 * 10^4