Non-overlapping Intervals

Medium#435sort by end

You get a list of intervals. Remove as few of them as possible so that no two of the rest overlap, and return how many you removed. Intervals that only touch, like [1, 3] and [3, 5], do not overlap. Our example: [4, 7], [0, 9], [8, 11], [1, 3], [10, 12], [3, 5], [6, 8] — the answer is 3.

435 Non-overlapping IntervalsWalkthrough · 1×

Example: [4, 7], [0, 9], [8, 11], [1, 3], [10, 12], [3, 5], [6, 8]. The intervals are drawn sorted by end; the ones kept are gathered in the bottom row.

[1, 3][3, 5][4, 7][6, 8][0, 9][8, 11][10, 12]kept0123456789101112
not looked at yetcurrent intervalkeptremoved

Sort by end: 3, 5, 7, 8, 9, 11, 12

01/25
restart · back · play · step
Speed
1function eraseOverlapIntervals(intervals):
2 sort intervals by end
3 removed = 0
4 lastEnd = -infinity
5 for each [start, end] in intervals:
6 if start >= lastEnd:
7 lastEnd = end
8 else:
9 removed = removed + 1
10 return removed
state
removed
–
lastEnd
–
start
–
end
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Removing the fewest is the same as keeping the most. Of all the intervals, the one that ends first is always worth keeping: any other choice ends later and leaves less room for the rest.
  2. After it, the same choice repeats on what starts at or after its end. Sorted by end, that is one pass: keep an interval if start ≥ lastEnd, otherwise it overlaps the last kept one, so remove it.
  3. Sorting by start would go wrong here: [0, 9] starts first, and keeping it would block [1, 3], [3, 5] and [6, 8].

Complexity

Time O(n log n): the sort; the pass after it is O(n). Memory O(1) besides what the sort needs.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.