Non-overlapping Intervals
You get a list of intervals as two arrays: interval i runs from starts[i] to ends[i]. Remove as few intervals as you can so that no two of the ones left overlap. Two intervals that only touch, where one ends at the exact point the other starts, do not overlap.
Write a function named eraseOverlapIntervals that returns the smallest number of intervals you have to remove.
Function
- startsinteger-array
- the start of each interval
- endsinteger-array
- the end of each interval, at the same index as its start
- Returnsinteger
- the fewest intervals to remove so that the rest do not overlap
Constraints
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- The intervals are not sorted. Two intervals may be identical.
Examples
- Input
- starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
- Output
- 2
- Explanation
- In start order the intervals are [1,4], [2,3], [3,6] and [5,7]. Keep [2,3] and [3,6], which only touch, and remove the other 2. You cannot keep three: [1,4] overlaps [2,3] and [3,6] overlaps [5,7], and any three of the four contain one of those pairs.
- Input
- starts = [0, 0, 0]ends = [5, 5, 5]
- Output
- 2
- Explanation
- The three intervals are all [0,5], so any two of them overlap. Only one can stay, and you remove the other
2.
- Input
- starts = [4, 1, 2]ends = [6, 2, 4]
- Output
- 0
- Explanation
- [1,2], [2,4] and [4,6] meet end to start and never overlap, so you remove nothing and the answer is
0.
+17 hidden tests on Submit
Follow-up
Suppose every interval also has a value, and you want the largest total value among intervals that do not overlap. Does keeping the interval that ends first still work? What would you use instead?
Hints
Open them one at a time. Each one gives away a little more.
Instead of choosing what to remove, think about what to keep. How is the largest set of intervals you can keep related to the answer?
Of all the intervals, the one that ends first leaves the most room for the rest. Some best answer always keeps it.
Sort the intervals by end and walk them while remembering the end of the last interval you kept. An interval that starts at or after that end is kept; every other interval counts as removed.
Solution
Removing the fewest intervals is the same as keeping the most intervals that do not overlap, so the answer is n minus that largest set. Trying every set to keep is exponential, and dynamic programming over chains of intervals brings it down to O(n²). One greedy rule finishes the job in O(n log n): of the intervals that still fit, always keep the one that ends first.
Keep or remove each interval
Correct, but does not finish on the largest tests
Intuition
Turn the question around. Removing the fewest intervals means keeping the most intervals that do not overlap, and the answer is n minus that number. So search for the largest set you can keep.
Sort the intervals by start and decide for each one, in that order, whether to remove it or keep it. You may keep it only if it starts at or after the end of the last interval you kept. That single check is enough: the kept intervals then form a chain where each one starts at or after the end of the one before, so no two of them overlap. Try both choices at every interval and take the better result.
In the first example the sorted intervals are [1,4], [2,3], [3,6], [5,7]. Keeping [1,4] blocks [2,3] and [3,6], which start before 4, and leaves room for [5,7]: 2 kept. Removing [1,4] and keeping [2,3] and then [3,6] also keeps 2. No branch reaches 3, so you remove 4-2 = 2.
Each interval can double the number of branches, so n intervals lead to up to 2^n paths. Thirty intervals that do not overlap already mean more than a billion calls, and the tests go up to 5000 intervals. The recursion also goes n levels deep: 5000 calls on the largest tests, past Python's default limit of 1,000.
Algorithm
- Sort the intervals by start, keeping each start with its own end.
- Define
mostKept(i, last): the most intervals you can keep from positionion, whenlastis the position of the latest kept interval (-1for none). - Past the end of the list, return
0. Otherwise start frommostKept(i+1, last), the result of removing intervali. - If interval
istarts at or after the end of intervallast, also try1 + mostKept(i+1, i)and keep the larger result. - Return
nminusmostKept(0, -1).
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
def most_kept(i, last):
# The most intervals you can keep among i..n-1, when interval last
# is the latest one kept so far (-1: nothing kept yet).
if i == n:
return 0
best = most_kept(i + 1, last) # remove interval i
if last == -1 or intervals[i][0] >= intervals[last][1]:
best = max(best, 1 + most_kept(i + 1, i)) # keep interval i
return best
return n - most_kept(0, -1)Longest chain with dynamic programming
Correct, but does not finish on the largest tests
Intuition
The search above answers the same question again and again: what is the longest chain that ends with this interval? Store that answer once per interval. Sort by start, and let chain[i] be the most intervals you can keep when interval i is the last one kept.
The interval kept right before i has to end at or before starts[i]. Every such interval comes earlier in the sorted order: it starts before it ends, so it starts before starts[i]. That gives chain[i] = 1 + chain[j] for the best earlier j with ends[j] ≤ starts[i], or 1 when no interval fits. The largest value in chain is the most you can keep.
For the first example, sorted as [1,4], [2,3], [3,6], [5,7], the values are 1, 1, 2 and 2: [3,6] can follow [2,3], and [5,7] can follow [1,4] or [2,3]. The longest chain is 2, so you remove 4-2 = 2.
Each interval looks back at every interval before it, which is n(n-1)/2 checks. With n = 5000 that is about 12.5 million checks: fine in a compiled language, too slow in the slower ones for the largest tests, and far behind the greedy below.
Algorithm
- Sort the intervals by start, keeping each start with its own end.
- Set
chain[i] = 1for every interval. - For each
iand eachj < iwithends[j] ≤ starts[i], setchain[i]tochain[j]+1when that is larger. - Return
nminus the largest value inchain.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
# chain[i]: the most intervals you can keep when interval i is the last one kept
chain = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
chain[i] = chain[j] + 1
return n - max(chain)Greedy: keep the interval that ends first
Intuition
Look at the interval with the smallest end. Some best answer always keeps it. Take any largest set of intervals you can keep and swap its earliest interval for this one. The new interval ends no later than the one it replaced, so it still ends at or before the start of the next kept interval. The set stays free of overlaps and keeps its size, so keeping the earliest end never costs you anything.
Once you keep it, every interval that starts before its end overlaps it and has to go. What is left is the same question on the intervals that start at or after that end, so apply the same rule again. In practice: sort by end, walk the list, and remember lastEnd, the end of the last kept interval. Keep an interval that starts at or after lastEnd; count any other interval as removed.
The first example sorted by end is [2,3], [1,4], [3,6], [5,7]. Keep [2,3], so lastEnd = 3. [1,4] starts at 1, before 3: remove it. [3,6] starts at 3, not before 3: keep it, lastEnd = 6. [5,7] starts at 5, before 6: remove it. Two removed.
Other keys look tempting and fail. Sorting by start keeps [0,100] when it covers [1,2], [3,4] and [5,6], and removes three intervals instead of one. Keeping the shortest interval fails on [1,5], [4,7], [6,10]: the short [4,7] overlaps both others, so keeping it costs two removals where one is enough. The end is the key that leaves the most room for everything after it.
The sort costs O(n log n) and the walk O(n). The sorted copy of the intervals takes O(n) space.
Algorithm
- Sort the intervals by end, keeping each end with its own start.
- Keep the first interval: set
lastEndto its end andremovedto0. - For each following interval, if it starts at or after
lastEnd, keep it and setlastEndto its end. - Otherwise add 1 to
removed. - Return
removed.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(ends, starts)) # by end time
removed = 0
last_end = intervals[0][0] # the interval that ends first is always kept
for end, start in intervals[1:]:
if start >= last_end:
last_end = end # it fits after the last kept interval: keep it
else:
removed += 1 # it overlaps the last kept interval: remove it
return removed
Pitfalls and edge cases
Most wrong answers come from the sort key or from the comparison at a touching point.
- Treating touching intervals as overlapping. With
start > lastEndinstead ofstart ≥ lastEnd, the chain [1,2], [2,4], [4,6] loses [2,4], which starts exactly where [1,2] ends, and the answer comes out 1 instead of 0. - Sorting by start and always keeping the earlier interval on an overlap. A wide [0,100] then pushes out [1,2], [3,4] and [5,6]. If you sort by start, keep whichever of the two overlapping intervals ends first.
- Comparing each interval with its neighbor in the sorted list instead of the last kept interval. After you remove [1,4], the next interval must be checked against the end of [2,3], not against 4.
- Sorting
startsandendsas two separate lists. Each end has to stay with its own start, or you compare a start with some other interval's end. - Returning how many intervals you keep. The question asks for the number removed, which is
nminus that.
Frequently asked questions4
What is the time complexity of Non-overlapping Intervals?
The greedy solution sorts the intervals by end in O(n log n) and then walks them once in O(n), so the total is O(n log n). The sorted copy of the intervals uses O(n) space. The dynamic programming version is O(n²), and trying every set to keep is O(2^n).
Why does sorting by end time give the fewest removals?
The interval that ends first can replace the first interval of any best answer without creating an overlap, because it ends no later. So some best answer keeps it, and after removing everything that overlaps it, the rest is the same problem on a smaller set. Repeating the argument shows every greedy choice is safe.
Can you sort by start time instead?
Yes, with a different rule on overlap. Walk the intervals by start, and when the next one overlaps the last kept interval, count one removal and keep whichever of the two ends first. It removes the same number of intervals as the sort by end and runs in the same O(n log n) time.
Is Non-overlapping Intervals the same as the activity selection problem?
It is the other side of it. Activity selection asks for the most intervals that do not overlap; this problem asks for the fewest to remove, which is n minus that number. The same greedy rule, keep the activity that ends first, solves both.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def eraseOverlapIntervals(starts, ends):
# Write code hereCase 1
Case 2
Case 3
Input
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
Expected
2