The problem
Find the fewest intervals to remove so that the rest don’t overlap. (Intervals that only touch, like [1,2] and [2,3], don’t overlap.)
Input: [1,2] [2,3] [3,4] [1,3] Output: 1 (remove [1,3])
Picture it
Picture a room with too many bookings. Sort them by finishing time. Keep the booking that finishes earliest, since it leaves the most room for the rest. Any booking that starts before the last kept one finishes must be cancelled.
How to recognise it
- You must remove the fewest intervals so that the rest do not overlap. That is the same as keeping the most intervals that do not overlap: removed = n − kept.
- "Keep the most non-overlapping intervals" is the classic activity selection problem, and it has a greedy solution (make the locally best choice and never undo it).
- The right local choice is the interval that finishes earliest: it leaves the most room for everything after it. That means sorting by end, not by start.
- Up to 10^5 intervals, so trying subsets or an O(n²) table is too slow.
- Touching intervals (
[1, 2]and[2, 3]) do not overlap here.
Start with brute force
A safe first approach is a table. Sort by end; keep[i] is the largest number of intervals you can keep if interval i is the last one kept. It is 1 plus the best keep[j] over earlier intervals that end by the time i starts.
def erase_brute(intervals):
ivs = sorted(intervals, key=lambda x: x[1])
keep = [1] * len(ivs) # keep[i]: most kept if ivs[i] is the last one kept
for i in range(len(ivs)):
for j in range(i):
if ivs[j][1] <= ivs[i][0]:
keep[i] = max(keep[i], keep[j] + 1)
return len(ivs) - max(keep, default=0)
Time is O(n²) and space O(n). For n = 10^5 that is about 5 × 10^9 pair checks, far too slow. (Trying every subset would be O(2^n), worse still.)
From brute force to the idea
- Find the waste. The table considers every earlier interval as a possible predecessor, but one choice is always good enough: keep the interval that ends first.
- Why earliest end is safe. Take any best selection and swap its first interval for the one that ends earliest overall. That one ends no later, so it clashes with nothing the first one did not clash with. The selection is still valid and just as large. Repeat the argument for the rest.
- Sort by end.
intervals.sort(key=lambda x: x[1])puts the earliest finisher first. - Track when the room is free.
free_atis the end of the last kept interval, starting at minus infinity so the first interval is always kept. - Keep or cancel. If
start >= free_at, the interval fits (touching is fine): keep it and setfree_at = end. Otherwise it overlaps a kept interval that ends no later than it does, so removing it is never worse: count it.
This is the key idea: greedily keep the interval that finishes first, and remove whatever clashes with it.
The key idea
Greedy by earliest end; count clashes. O(n log n).
Python solution
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # earliest finish first
removed, free_at = 0, -inf
for start, end in intervals:
if start >= free_at:
free_at = end # keep it
else:
removed += 1 # clashes with a kept booking
return removedLeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Table (brute force) | O(n²): each interval checks every earlier one | O(n): the table and the sorted copy |
| Greedy by end (shown code) | O(n log n): the sort; the sweep is O(n) | O(1) besides the sort, which works in place (Python's sort may use up to O(n) temporary memory) |
Edge cases
- One interval: kept, so the answer is 0.
- Touching chain (
[[1, 2], [2, 3], [3, 4], [1, 3]]): returns 1 (remove[1, 3]), becausestart >= free_atallows touching. - Identical intervals (
[[1, 2], [1, 2], [1, 2]]): returns 2; only one copy can stay. - One long interval covering short ones (
[[1, 100], [2, 3], [4, 5]]): returns 1, removing the long one. - Negative values: fine, because
free_atstarts at minus infinity rather than 0. - The input is changed:
sort()reorders the caller's list. The shown code also needsfrom math import inf.
Common mistakes
- Sorting by start and keeping the first interval, which keeps a long early interval that blocks many short ones.
- Writing
start > free_at, which treats touching intervals as overlapping. - Starting
free_atat 0, which wrongly removes an interval that starts at a negative time. - Counting the kept intervals and returning that, instead of n minus it.
Balloons are intervals on a line, and an arrow shot at x bursts every balloon with start ≤ x ≤ end. Find the fewest arrows to burst all of them. For [[10, 16], [2, 8], [1, 6], [7, 12]] the answer is 2. Describe your approach, then write it if you like.
Compare with our answer
Same greedy. Sort by end and shoot the first arrow at the end of the balloon that finishes first: that point hits as many balloons as any point that still hits it. Each balloon that starts after the last arrow needs a new arrow. Unlike the meetings, a balloon that only touches the arrow's position is burst, so the test is start > pos.
from math import inf
def find_min_arrows(points):
points = sorted(points, key=lambda p: p[1])
arrows, pos = 0, -inf
for start, end in points:
if start > pos: # not hit by the last arrow
arrows += 1
pos = end # shoot at its right edge
return arrows
Time O(n log n), space O(n) for the sorted copy.
A strong answer mentions: sorting by end, shooting at the earliest end, and why touching now counts as a hit (> instead of >=).
1. One lecture hall must host as many talks as possible from a list of requested time slots. Which approach fits best?
This is activity selection: the earliest finisher leaves the most room. Earliest start keeps long early talks; shortest first fails for a short talk that straddles two longer ones that fit side by side.
2. Why does sorting by start instead of end give the wrong answer for [[1, 100], [2, 3], [4, 5]]?
Sorting by start keeps [1, 100] and removes 2 intervals; the right answer is 1 (remove the long one). Sorting by end keeps [2, 3] and [4, 5].
3. A learner writes if start > free_at:. Which input now gives a wrong answer?
With >, [2, 3] no longer fits after [1, 2], so it is removed too and the code returns 2. The other inputs have no intervals that only touch, so > and >= agree.
Score 60% or more and the lesson is marked complete.