Non-overlapping Intervals

Non-overlapping Intervals is the classic greedy interval problem. It teaches the single most important move for interval questions: sort by the right edge, then sweep left to right keeping whatever finishes earliest.

The slow way first

Removing the minimum number of intervals is the same as keeping the maximum number of non-overlapping ones. You could try every subset of intervals and check which valid combinations are largest — but that is exponential, O(2ⁿ), hopeless for any real input.

The question to ask: when two intervals fight for the same space, which one should I keep? The answer is the one that frees up the timeline soonest — the interval with the smallest end. Keeping it can only leave more room for everything that follows.

The idea: keep the earliest finisher

Sort all intervals by their end value. Walk through them left to right, tracking last_end, the end of the most recently kept interval. For each interval:

• If its start >= last_end, it does not overlap the kept set — keep it and update last_end.
• Otherwise it overlaps — remove it (add one to the count) and leave last_end alone.

Because we always keep the earliest-ending interval, every greedy choice is safe: no other choice could leave more room for the rest.

Walk through it

Step through the animation. The bars are already sorted by end. The marker tracks last_end. [1,2] and [2,3] are kept (each starts at or after the previous end). [1,3] starts at 1, which is before last_end = 3, so it overlaps and gets dimmed and removed. [3,4] starts exactly at 3 and is kept. One removal total.

Pseudocode

sort intervals by their end value
removals = 0
last_end = negative infinity
for each interval (start, end):
    if start >= last_end:        # no overlap, keep it
        last_end = end
    else:                        # overlaps, remove it
        removals += 1
return removals

The Python solution

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda iv: iv[1])
    removals = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            last_end = end
        else:
            removals += 1
    return removals

• intervals.sort(key=lambda iv: iv[1]) sorts by end (iv[1]) — the heart of the greedy choice.
• last_end starts at -inf so the very first interval is always kept.
• start >= last_end is the no-overlap test. Endpoints touching (start == last_end) is allowed, so we use >=, not >.
• When we keep an interval we advance last_end to its end; when we remove one we change nothing but the count.
• removals is the answer — the fewest intervals to delete.

Complexity

The sort dominates at O(n log n); the sweep is a single linear pass and the only extra state is a counter and last_end, so O(1) extra space (ignoring the sort).

When this pattern shows up

Practice