progress

~/problems / Greedy

Non-overlapping Intervals

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or play this problem's boss fight .

Write erase_overlap_intervals(intervals: list[list[int]]) -> int.

Each interval is [start, end] with start < end. Return the minimum number of intervals to remove so that no two of the remaining intervals overlap. Intervals that only touch, like [1, 3] and [3, 6], do not overlap.

Example: [[1, 3], [2, 4], [3, 5], [1, 2]] gives 2. Keep [1, 2], [2, 4] (or [1, 2], [3, 5]).

Four intervals on a line from 1 to 5; keeping 1-2 and 2-4, which only touch, means removing the two that overlap them, 1-3 and 3-5.

More examples: [[0, 5], [5, 10]] gives 0, and an empty list gives 0.

Constraints: up to 10^5 intervals, endpoints between -5 * 10^4 and 5 * 10^4.

⭐ Bonus: a speed test with 100,000 intervals earns a star in O(n log n). Comparing all pairs, or an O(n²) DP, is too slow for it.

Show hint

removing the fewest is the same as keeping the most. Among the intervals you could keep next, which one leaves the most room for the rest?

Topic: Greedy with sorting. Sort, then take the locally best choice; prove it with an exchange argument.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc