Non-overlapping Intervals

Signal

"Minimum removals to eliminate all overlap" is the activity-selection greedy in disguise: instead of asking "how many can I remove," flip it to "how many can I keep" — and keeping is easiest when you always favor the interval that frees up time soonest.

Approach

Sort intervals by end time, not start. Greedily keep the first interval, then scan the rest: if the next interval starts before the last kept interval ends, it overlaps — discard it (count a removal) rather than the one you already kept, since the kept interval — sorted by end — leaves the most room for everything after it. If it doesn't overlap, keep it and it becomes the new "last kept."

Skeleton

sort intervals by end
last_end = -infinity
removals = 0
for interval in intervals:
    if interval.start >= last_end:
        last_end = interval.end   # keep it
    else:
        removals += 1              # discard it, last_end unchanged
return removals

Solution

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda iv: iv[1])
    last_end = float("-inf")
    removals = 0

    for start, end in intervals:
        if start >= last_end:
            last_end = end
        else:
            removals += 1

    return removals

Complexity

O(n log n) time — the sort dominates; the greedy scan is O(n). O(1) extra space beyond the sort.

Pitfalls

• Sorting by start instead of end — that's the right key for merge-intervals, but here it lets a long early interval crowd out several short later ones that could otherwise all be kept.
• On a discard, don't advance last_end to the discarded interval's end — keep whichever of the two conflicting intervals ends sooner (which, sorted by end, is always the one you already kept).
• Touching endpoints (start == last_end) count as not overlapping in the standard version of this problem — use >=, not >.