Non-overlapping Intervals
Problem Statement
Given an array of intervals, return the minimum number of intervals you need to remove so the rest of the intervals are non-overlapping.
Input
An integer matrix intervals, where each row is a closed interval [start, end].
Output
An integer: the minimum number of intervals to remove so no remaining intervals overlap.
Constraints
- •
1 <= intervals.length <= 10^5 - •
intervals[i].length == 2 - •
-5 * 10^4 <= starti < endi <= 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
- Recognise minimum removals as the complement of keeping the maximum number of compatible intervals.
- Explain why sorting by end time gives the safest greedy choice.
- Use **nextStart < lastEnd** as the overlap test for accepted intervals.
- Count removals without physically deleting intervals from the array.
Intuition
Pattern Recognition
The signal is remove the fewest intervals so the survivors do not overlap. The trap is merging intervals, which changes the ranges and does not answer how many original intervals must be removed. Another trap is sorting by start and keeping a long interval that blocks many short ones.
This is an interval scheduling problem in disguise. To minimise removals, maximise how many intervals you keep. The greedy choice is to keep the interval that ends earliest, because it leaves the most room for everything that follows. After sorting by end, whenever the next interval overlaps the last kept interval, remove the next interval and keep the earlier-ending one already chosen.
Common mistakes
- ×Merging overlapping intervals instead of counting how many original intervals must be removed.
- ×Sorting by start and keeping a long early interval that blocks better future choices.
- ×Treating **start == lastEnd** as an overlap even though touching endpoints are allowed here.
- ×Updating **lastEnd** after counting a removal, which accidentally keeps the later-ending conflicting interval.
Algorithm Explanation
Key idea
Sort intervals by increasing end. Keep the first interval and remember its end as lastEnd. For each next interval, if start < lastEnd, it overlaps the last kept interval, so count one removal and keep lastEnd unchanged. Otherwise keep the interval and update lastEnd to its end.
Interval walkthrough
Use intervals = [[1,2],[2,3],[3,4],[1,3]]. Sorted by end, the order is [1,2], [1,3], [2,3], [3,4]. On the number line 1--2--3--4, keep [1,2] first, so lastEnd = 2. The interval [1,3] starts at 1, before 2, so it overlaps and is removed; keeping [1,2] is better because it ends earlier. The interval [2,3] starts exactly at 2, so it can stay and lastEnd becomes 3. The interval [3,4] starts at 3, so it can stay too. Total removals: 1.
Algorithm
- Return 0 when there are zero or one intervals.
- Sort intervals by increasing end value.
- Set lastEnd to the end of the first sorted interval.
- Scan the remaining intervals in sorted order.
- If the current start is less than lastEnd, increment removals and do not update lastEnd.
- Otherwise keep the current interval and update lastEnd to its end.
- Return removals.
Solutions
Solution: Sort by end and count rejected intervals
Use this for the canonical greedy proof. It directly maximises the number of intervals kept, which minimises removals.
Sort by interval end time, then keep intervals only when they start at or after the last kept end. If an interval starts before lastEnd, count it as removed because the already kept interval ends no later.
Step-by-step
- Handle arrays with at most one interval by returning 0.
- Sort all intervals by end time, using start time only as a stable tie-breaker.
- Keep the first interval and store its end in lastEnd.
- For each next interval, count a removal when start < lastEnd.
- Only update lastEnd when the current interval is kept.
- Return the total number of removals.
O(n log n)
O(n)
Sorting dominates the runtime. The greedy scan stores only two integers, while Java sorting may allocate temporary storage.
Java implementation
Dry Run
Sample input
intervals = [[1,2],[2,3],[3,4],[1,3]]. After sorting by end: [[1,2],[1,3],[2,3],[3,4]].
| interval | lastEnd before | overlap test | decision | removals |
|---|---|---|---|---|
| [1,2] | none | first kept interval | keep, lastEnd = 2 | 0 |
| [1,3] | 2 | 1 < 2 | remove current, keep earlier end 2 | 1 |
| [2,3] | 2 | 2 >= 2 | keep, lastEnd = 3 | 1 |
| [3,4] | 3 | 3 >= 3 | keep, lastEnd = 4 | 1 |
Sorting by end makes the conflict decision local. When [1,3] conflicts with [1,2], the shorter earlier-ending interval is always at least as good for future intervals.
Interview Tips
Phrase the proof as keep as many as possible, then removals are n - kept or equivalently count rejected intervals. Sorting by end is the key: the earliest finishing compatible interval leaves the most remaining space. Be explicit that start == lastEnd is allowed, so the removal test is start < lastEnd.
Likely follow-ups
- Can you return the intervals that remain instead of only the removal count?
- How would the answer change if touching endpoints were considered overlapping?
- How would you solve the weighted version where each interval has a removal cost?
- Can you compute the same answer by sorting by start and replacing the current end with the smaller end on conflict?
Similar Problems
Key Takeaways
- Minimum removals equals choosing the maximum number of non-overlapping intervals to keep.
- Sorting by end time makes the earliest-finishing interval the safest greedy keeper.
- On conflict, count a removal and keep **lastEnd** unchanged.
- Endpoint touching is allowed here, so only **start < lastEnd** is an overlap.