Given a list of intervals, remove the minimum number so the remaining intervals do not overlap.
You are given a collection of intervals, where each interval is represented as a pair [start, end].
Remove the minimum number of intervals so that no two remaining intervals overlap. Two intervals overlap if they share any point in time. In this problem, an interval that ends at time x and another that starts at time x do not overlap.
Return the minimum number of intervals you must remove.
A good solution should keep as many non-overlapping intervals as possible, which is closely related to interval scheduling.
intervals of length n[start, end] with start <= end1 <= n[a, b] and [b, c] are compatibleExample 1
Input
intervals = [[1,2],[2,3],[3,4],[1,3]]
Output
1
Explanation
Keeping [1,2], [2,3], and [3,4] leaves one overlapping interval to remove: [1,3].
Example 2
Input
intervals = [[1,2],[1,2],[1,2]]
Output
2
Explanation
At most one interval can remain without overlap, so two must be removed.
Example 3
Input
intervals = [[1,100],[11,22],[1,11],[2,12]]
Output
2
Explanation
One optimal choice is to keep [1,11] and [11,22], removing the other two overlapping intervals.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.