Non-overlapping Intervals
Problem
[start, end]. Return the
fewest intervals you must delete so that no two remaining intervals overlap.
Intervals that only touch at an endpoint (e.g. [1,2] and [2,3])
do not count as overlapping.[[1,2],[2,3],[3,4],[1,3]]Output1[[1,2],[1,2],[1,2]]Output2[[1,2],[2,3]]Output01 ≤ n ≤ 105 · -5·104 ≤ start < end ≤ 5·104
Try it yourself
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
}
}
Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.
Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.
Open the Intervals & Line Sweep guide →Approaches
Brute ForceRecursion: Keep or Skip Each Interval
O(2n)Space O(n)Sort by start. For every interval try both choices: skip it, or keep it if it
starts at or after the end of the last kept one. The best keep-count over all subsets
gives the answer n − kept.
public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); return intervals.length - maxKeep(intervals, 0, Integer.MIN_VALUE); } private int maxKeep(int[][] iv, int i, int prevEnd) { if (i == iv.length) return 0; int skip = maxKeep(iv, i + 1, prevEnd); if (iv[i][0] < prevEnd) return skip; // overlaps the last kept interval return Math.max(skip, 1 + maxKeep(iv, i + 1, iv[i][1])); }
Explores every subset — correct, but exponential.
BetterDP (Longest Non-overlapping Chain)
O(n2)Space O(n)After sorting by start, dp[i] = most intervals keepable in a chain
that ends with interval i = 1 + best dp[j] over earlier
j with endj ≤ starti. Same shape as
Longest Increasing Subsequence.
public int eraseOverlapIntervals(int[][] intervals) { int n = intervals.length, best = 0; Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); int[] dp = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (intervals[j][1] <= intervals[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1); } best = Math.max(best, dp[i]); } return n - best; }
Polynomial, but quadratic — too slow for n = 105.
OptimalGreedy — Sort by End
O(n log n)Space O(1) excl. sortSort by end and sweep, tracking end of the last kept
interval. If the next one starts before end it overlaps → delete it;
otherwise keep it. Exchange argument: swapping any optimal first pick for the
earliest-ending interval never causes a new overlap.
public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); int end = intervals[0][1], count = 0; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] < end) count++; // overlap -> remove it else end = intervals[i][1]; // keep it } return count; }
Dry runsorted by end: [1,2],[2,3],[1,3],[3,4]
- i=01,2i2,31,33,4keep, end=2
- i=11,22,3i1,33,42 ≥ 2 keep, end=3
- i=21,22,31,3i3,41 < 3 remove, count=1
- i=31,22,31,33,4i3 ≥ 3 keep → 1 ✔
One sort and one pass — the classic activity-selection greedy.
end = min(end, cur[1]).At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursion: Keep or Skip Each Interval | O(2n) | O(n) |
| Better | DP (Longest Non-overlapping Chain) | O(n2) | O(n) |
| Optimal | Greedy — Sort by End | O(n log n) | O(1) excl. sort |
- Treating touching intervals as overlapping — use
start < end, not≤. - Sorting by start and always deleting the later interval — must drop the one ending later.
- Comparator
a[1] - b[1]can overflow for extreme values; useInteger.compare.
- Reframe first: “remove fewest” = “keep the most non-overlapping”.
- Justify earliest-end greedy with a one-line exchange argument.
- Mention it is the same as Minimum Arrows to Burst Balloons (452).