Non-overlapping Intervals
Problem Statement
Given an array of intervals, return the minimum number of intervals you need to remove so that the remaining intervals are non-overlapping. Intervals that only touch at an endpoint, such as [1,2] and [2,3], are non-overlapping.
Input
An integer matrix intervals, where each row is an interval [start, end].
Output
An integer: the minimum number of intervals to remove so all remaining intervals are pairwise non-overlapping.
Constraints
- •
1 <= intervals.length <= 10^5 - •
intervals[i].length == 2 - •
-5 * 10^4 <= start < end <= 5 * 10^4
Examples
Example 1
intervals = [[1,2],[2,3],[3,4],[1,3]]
1Example 2
intervals = [[1,2],[1,2],[1,2]]
2Example 3
intervals = [[1,2],[2,3]]
0Learning Objectives
- Transform minimum removals into maximizing the number of intervals kept.
- Recognise the earliest-finish greedy rule for interval scheduling.
- Use an exchange argument to justify keeping the interval with the smallest end.
- Distinguish overlap rules for removal from merge rules for closed intervals.
Intuition
The greedy insight is to keep as many intervals as possible, then removals are simply n - kept. To leave room for future intervals, the safest interval to keep is the one that finishes earliest among the intervals currently competing for the next slot.
The tempting wrong idea is to sort by start and keep the first interval you see. That can trap you with a long interval that blocks several short intervals. Sorting by end makes the local choice future-friendly: each kept interval leaves the maximum remaining timeline for everything after it.
Common mistakes
- ×Sorting by start and keeping long intervals that block better future choices.
- ×Using **start <= currentEnd** as overlap; for this problem, touching endpoints are allowed, so overlap is **start < currentEnd**.
- ×Counting kept intervals but returning that count instead of removals.
- ×When two intervals overlap, advancing the current end to the larger end instead of keeping the smaller end.
Algorithm Explanation
Greedy strategy
Sort intervals by increasing end. Keep the first interval because it finishes earliest. Then keep every next interval whose start is at least the end of the last kept interval. Every interval that starts before that end must be removed.
Why it works
Among all intervals that could be chosen next, the one with the earliest end leaves the most room for future intervals. Choosing a later-ending interval can only reduce the set of intervals that remain compatible afterward.
Proof of correctness
Take an optimal solution that keeps the maximum number of non-overlapping intervals. Look at the first interval kept by that solution. The greedy algorithm chooses the interval with the earliest end among all intervals. If the optimal solution chose a different first interval, replace it with the greedy interval. The greedy interval ends no later, so every interval that was compatible after the original first interval is still compatible after the greedy one. The number of kept intervals does not decrease. Applying the same exchange after each greedy choice shows there is an optimal solution that makes exactly the greedy choices. Therefore the greedy kept count is maximum, and the resulting removal count is minimum.
Algorithm
- Sort intervals by end, using start as a tie-breaker.
- Set currentEnd to the end of the first interval and removed to 0.
- Scan the remaining intervals.
- If start < currentEnd, the interval overlaps the last kept interval, so increment removed.
- Otherwise, keep the interval and update currentEnd to its end.
- Return removed.
Solutions
Solution: Earliest finishing interval sweep
This is the classic activity-selection greedy rule. By sorting by end, every time we keep an interval we choose the compatible interval that leaves the most room for the rest of the schedule.
Step-by-step
- Sort intervals by increasing end time, with start as a deterministic tie-breaker.
- Keep the first interval and remember its end.
- For each later interval, compare its start to the end of the last kept interval.
- If it overlaps, remove it and keep the earlier end already stored.
- If it does not overlap, keep it and move the current end forward.
O(n log n)
O(1)
Sorting dominates. Apart from the sort implementation, the sweep uses constant extra space.
Java implementation
Dry Run
Sample input
intervals = [[1,2],[2,3],[3,4],[1,3]]. Sort by end and track the end of the last kept interval plus the removal count.
| step | interval after end-sort | current kept end before | decision | current kept end after | removed count |
|---|---|---|---|---|---|
| 1 | [1,2] | none | Keep the earliest ending interval. | 2 | 0 |
| 2 | [1,3] | 2 | 1 < 2, so remove this overlapping interval. | 2 | 1 |
| 3 | [2,3] | 2 | 2 >= 2, so keep it and move the end to 3. | 3 | 1 |
| 4 | [3,4] | 3 | 3 >= 3, so keep it and move the end to 4. | 4 | 1 |
The greedy sweep keeps three intervals and removes one. Since three is the maximum possible kept count, one removal is minimum.
Interview Tips
Frame the problem as activity selection: minimize removals by maximizing compatible intervals kept. The key phrase interviewers expect is earliest finishing time. Also be careful with the boundary rule: unlike Merge Intervals, endpoint equality is allowed here, so [1,2] and [2,3] can both remain.
Likely follow-ups
- How would you return the intervals removed rather than only the count?
- How would the rule change if intervals touching at endpoints were considered overlapping?
- How would you solve the weighted version where each interval has a value?
- How would you handle intervals arriving online without sorting all of them first?
Similar Problems
Key Takeaways
- Minimum removals equals total intervals minus maximum intervals kept.
- For interval scheduling, choosing the earliest finishing compatible interval is safe.
- When an overlap appears after end-sorting, remove the current interval and keep the smaller end.
- Endpoint equality is compatible in this problem.