-
Notifications
You must be signed in to change notification settings - Fork 0
162 — Non overlapping Intervals
LeetCode 435 · Medium. Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Picture a single classroom and a stack of activity requests, each with a start and end time, more of them than the room can ever host without conflicts. You want to throw out as few requests as possible so whatever's left never double-books the room. The classic trick: sort every request by its end time, not its start time, and walk through greedily keeping whichever activity finishes soonest whenever there's a choice. An activity that ends early frees up the room fastest for everything still to come — so keeping the earliest-ending option out of any overlapping cluster never costs you a future opportunity, while keeping a later-ending one might. Whatever a later, greedier look-ahead could find, this local "always keep the one that ends first" choice already matches.
"Minimum number of intervals to remove so the rest don't overlap" is the classic interval-scheduling-maximization tell — phrased as a removal count, but really asking "what's the largest subset of pairwise non-overlapping intervals I can keep?" That framing is the signature for greedy-by-earliest-end-time: sort by end time, then walk through keeping every interval that doesn't conflict with the last one you kept.
Sort by end time, then use dynamic programming: dp[i] is the length of the longest chain of non-overlapping intervals that can end with sorted[i], built by checking every earlier interval sorted[j] that finishes before sorted[i] starts. The answer is n minus the longest chain found anywhere.
func eraseOverlapIntervalsBruteForce(_ intervals: [[Int]]) -> Int {
guard !intervals.isEmpty else { return 0 }
let sorted = intervals.sorted { $0[1] < $1[1] }
let n = sorted.count
var dp = [Int](repeating: 1, count: n) // dp[i] = longest non-overlapping chain ending at i
for i in 0..<n {
for j in 0..<i {
if sorted[j][1] <= sorted[i][0] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
}
let longestChain = dp.max() ?? 0
return n - longestChain
}
// smoke test
print(eraseOverlapIntervalsBruteForce([[1,2],[2,3],[3,4],[1,3]])) // 1
print(eraseOverlapIntervalsBruteForce([[1,2],[1,2],[1,2]])) // 2
print(eraseOverlapIntervalsBruteForce([[1,2],[2,3]])) // 0
print(eraseOverlapIntervalsBruteForce([])) // 0Big-O: O(n^2) time — the nested loop compares every interval against every earlier one. O(n) space for the dp array.
Sort by end time, then greedily keep a running "last kept end time." Any interval that starts before that boundary must be discarded (it overlaps whatever's already kept); anything else gets kept, and its end becomes the new boundary.
func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
guard !intervals.isEmpty else { return 0 }
let sorted = intervals.sorted { $0[1] < $1[1] }
var removals = 0
var lastEnd = sorted[0][1]
for interval in sorted.dropFirst() {
if interval[0] < lastEnd {
// overlaps the interval we've already committed to keeping — discard this one
removals += 1
} else {
// no overlap — keep it, and it becomes the new boundary
lastEnd = interval[1]
}
}
return removals
}
// smoke test — same cases as the brute force
print(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])) // 1
print(eraseOverlapIntervals([[1,2],[1,2],[1,2]])) // 2
print(eraseOverlapIntervals([[1,2],[2,3]])) // 0
print(eraseOverlapIntervals([])) // 0Big-O: O(n log n) time — dominated by the sort; the greedy sweep itself is a single linear pass. O(1) extra space beyond the sort.
The brute-force DP considers, for every interval, every possible earlier interval it could chain onto — genuinely correct, but it re-derives from scratch a fact that greedy can track with a single running number. Once sorted by end time, the interval that ends soonest among any overlapping cluster is always the safest one to keep: it leaves the most room for whatever comes next, so no other choice in that cluster could ever lead to a longer kept chain. That guarantee means you never need to compare an interval against every earlier one — only against the end time of whatever you most recently decided to keep — collapsing the O(n^2) comparison grid down to one boundary value updated in a single pass.
- Merge Intervals — same family of "sort the ranges, then make one pass" problems, though this one sorts by end time instead of start time because the goal is scheduling, not merging.
-
Greedy — textbook greedy-by-earliest-end-time interval scheduling: keeping the option that frees up the room soonest is a single irrevocable local choice that's never revisited, the same shape as Jump Game's
farthesttracker. -
Arrays and Strings — both versions scan a plain array of
[start, end]pairs after sorting.
Non-overlapping Intervals is sort-by-end-time-and-keep-the-soonest-finisher — whichever activity ends first out of any overlapping cluster is always the safe one to keep.
- Why does the greedy optimal sort by end time, while Merge Intervals sorts by start time? What would go wrong if
eraseOverlapIntervalssorted by start time instead? - Trace
eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])by hand after sorting by end time. Which interval gets discarded, and why is[1,3]the one that has to go rather than[2,3]? - Why does
interval[0] < lastEnd(strict less-than) correctly treat touching intervals like[1,2]and[2,3]as non-overlapping? - The brute force's
dp[i]considers chaining onto every earlier intervalsorted[j]withsorted[j][1] <= sorted[i][0]. Why does the greedy version get away with comparing only against the single most recent kept interval instead of scanning all of them?