Non-overlapping Intervals

Find the fewest ranges to remove so the rest do not overlap.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Non-overlapping Intervals: Sort by end time; keep a candidate exactly when its start reaches the last kept end.

Input and goalFind the fewest ranges to remove so the rest do not overlap.

Initialize after sortingSorting by end gives [1,3], [2,4], [3,5], [5,7]. Start with last_end=-inf and removed=0.

[1,3]

[2,4]

[3,5]

[5,7]

exampleintervals = [[1,3], [3,5], [2,4], [5,7]]sortedByEnd[1,3], [2,4], [3,5], [5,7]lastEnd-infremoved0

Recognize it

The task asks for the fewest removals needed to leave non-overlapping ranges, which is equivalent to keeping the largest compatible subset.

Keep true

After each candidate, the kept intervals do not overlap, last_end is the end of the latest kept interval, and the greedy choices leave at least as much future room as any alternative of the same size.

Reuse it

When selecting the most compatible time ranges, an earlier finishing accepted choice never blocks a range that a later-finishing choice could keep; reuse this exchange argument for activity and reservation scheduling.

Pattern: Greedy interval scheduling.

Simple idea: Keep the range that ends first. It leaves the most room for future ranges. After sorting by end, remove any range that starts before the last kept end.

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
   removed = 0
   last_end = float("-inf")

   for start, end in sorted(intervals, key=lambda interval: interval[1]):
      if start < last_end:
         removed += 1
      else:
         last_end = end
   return removed

Cost: $O(n\log n)$ time and $O(1)$ extra space, not counting sorting.