Given a list of intervals, remove the minimum number so the remaining intervals do not overlap.
Problem
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.
Intuition
A good solution should keep as many non-overlapping intervals as possible, which is closely related to interval scheduling.
Input Format
- An array
intervalsof lengthn - Each element is a pair
[start, end]withstart <= end
Output Format
- Return a single integer: the minimum number of intervals to remove.
Constraints
1 <= n- Intervals are finite integer ranges
- Use the non-overlap rule where
[a, b]and[b, c]are compatible
Example 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.
Show 1 more example
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
Unlock deeper context for this problem
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.