Non-overlapping Intervals

How you get there

1. 1Keeping the most intervals is the same as removing the fewest.
2. 2Sort by end time and always keep the earliest-finishing compatible interval.
3. 3That greedy choice provably leaves the most room for the rest.

Solution

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda pair: pair[1])    # by END, not start
    kept = 0
    current_end = float("-inf")

    for start, end in intervals:
        if start >= current_end:
            kept += 1
            current_end = end
    return len(intervals) - kept

Time

O(n log n)

Space

O(1)

What goes wrong

Sorting by start time is the intuitive choice and is wrong — one long early interval blocks many short ones.