Sweeping intervals

Interval problems arrive looking like a dozen unrelated puzzles: merge these, count the rooms, can this meeting fit, how many can I keep. They are one algorithm with three settings.

Sort by one endpoint. Sweep left to right. Carry exactly one piece of state. Which endpoint you sort by and what the state is are the only decisions, and getting the first one wrong is what makes a correct-looking greedy answer wrong.

The three settings

Goal	Sort by	State carried
Merge overlapping intervals	start	the interval being built
Keep the most non-overlapping intervals	end	the end of the last one kept
Maximum overlap at any instant	events, not intervals	a running count

The table is the lesson. The sort key differs per row because each sweep needs a different quantity settled by the time it looks at an interval: merging needs starts, so nothing already emitted can be reopened; selection needs ends, so the earliest finish is committed first; counting needs the two endpoints split apart, because one interval changes the running total at two different times.

The overlap test, stated once

Two intervals a and b overlap when a.start <= b.end and b.start <= a.end.

That condition is hard to see directly and easy to see by negation: they miss each other only when one finishes before the other starts, so the miss condition is a.end < b.start or b.end < a.start. Negate it and the two clauses above fall out.

The comparison operator is where the requirement hides. If touching counts — [1, 2] and [2, 3] share the instant 2 — use <=. If the intervals are half-open, as meeting times usually are because a room frees at exactly the moment the next booking starts, use <. Ask which one it is; do not guess.

Merging: sort by start, carry the interval

Sorting by start means every interval you visit either extends the one you are holding or begins a new one. Nothing you have already emitted can be affected by what comes later, which is the property that makes a single pass legal.

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])          # start ascending
    out = []
    for s, e in intervals:
        if out and s <= out[-1][1]:               # touches the carried end
            out[-1][1] = max(out[-1][1], e)       # extend, never assign
        else:
            out.append([s, e])
    return out

Four intervals sorted by start, swept into two merged intervals with a gap between them100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

max is the whole correctness of the merge. Write out[-1][1] = e instead and [[1, 10], [2, 3]] returns [[1, 3]] — a contained interval silently shrinks the answer. It is the most common interval bug there is, and it survives every example where the intervals happen to be the same length.

Cost is O(n log n) for the sort plus O(n) for the sweep, so the sort dominates. At n = 10⁵ that is about 10⁵ × 17 ≈ 1.7 × 10⁶ comparisons — roughly 17 ms against the 10⁸ simple operations per second worth budgeting for.

Selecting the most non-overlapping: sort by end

Now the intuition that worked above fails. Sorting by start and taking greedily gives the wrong answer on [[1, 10], [2, 3], [4, 5]]: you take [1, 10], it blocks everything, and you keep one interval where two fit.

Sort by end instead and take any interval that starts at or after the last end you kept:

def max_non_overlapping(intervals):
    intervals.sort(key=lambda iv: iv[1])          # end ascending
    kept, last_end = 0, float('-inf')
    for s, e in intervals:
        if s >= last_end:
            kept, last_end = kept + 1, e
    return kept

The exchange argument is short enough to say out loud: among all intervals that still fit, the one that finishes earliest leaves the most room for everything after it, so swapping it into any optimal solution never reduces the count. Earliest finishing time, not earliest start, not shortest duration.

The same code answers "how many do I delete to remove all overlaps" — that is n minus the count kept — which is why these two questions are the same question.

Counting concurrency: events, not intervals

Merging tells you where something is happening. It throws away how much: a merged [1, 6] looks the same whether one interval covers it or forty do. When the question is "how many rooms do I need" or "what is the peak number of concurrent streams", the interval is the wrong unit. The endpoint is.

Split each interval into two events, +1 at the start and -1 at the end, sort the events by time, and take a running sum. The running sum after each event is the number of intervals currently open; the maximum it reaches is the answer.

def max_concurrent(intervals):
    events = []
    for s, e in intervals:
        events.append((s, +1))
        events.append((e, -1))
    events.sort()                                 # (time, delta): -1 before +1
    best = cur = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

The tie rule is carried by the tuple key rather than by an if. At equal times -1 sorts before +1, so an interval ending at t and another starting at t do not count as concurrent — the half-open reading. If touching should count, invert the deltas in the key so the opening is processed first. This is the tuple key doing work that would otherwise be a comparator and a paragraph of prose.

Cost: 2n events, one sort, one pass. At n = 10⁶ intervals that is 2 × 10⁶ events and roughly 2 × 10⁶ × 21 ≈ 4 × 10⁷ comparisons.

When the times are small integers, drop the sort

If the times are bounded — minutes in a day, k = 1,440; days in a year, k = 365 — you do not need to sort anything. Allocate an array of length k + 1, add +1 at each start index and −1 at each end index, then take one prefix sum. That is O(n + k) with tiny constants: at n = 10⁶ bookings across k = 1,440 minutes that is two writes per booking plus one pass over the array, 2 × 10⁶ + 1,440 ≈ 2 × 10⁶ steps against 4 × 10⁷ comparisons, roughly twenty times less work. Same idea, same reason, as sorting without comparisons: a known, small key range beats a general sort.

The difference array also answers the range-update question the sort cannot: add 1 to every position in [s, e) for a million ranges, then read the final array once.

In an interview

Say which endpoint you are sorting by and why, before writing the loop. "Merging needs starts, because then nothing already emitted can change; selection needs ends, because earliest finish leaves the most room." That single sentence is most of what is being tested.

The second thing being tested is whether you notice the question is about depth rather than coverage. As soon as the words are "how many at once", "peak", or "minimum rooms", say "this is a sweep over +1/−1 events" and the rest is bookkeeping.

The mistake that loses points: writing out[-1][1] = e instead of out[-1][1] = max(out[-1][1], e) in the merge, then testing only on examples where no interval contains another. Give yourself [[1, 10], [2, 3]] as a standing edge case, the way the solving loop asks you to.

Check yourself

You sorted by start and greedily kept every interval that fits. On which input does that give the wrong count, and what is the fix?

[[1, 10], [2, 3], [4, 5]]: it keeps one, the answer is two. Sort by end instead — the earliest finishing interval leaves the most room for the rest.

One million bookings, each a start and end minute within a single day. Peak concurrency — sort the events or not?

Not. The key range is 1,440, so a difference array over minutes is O(n + k): one +1 and one −1 per booking plus a 1,440-step prefix sum, 2 × 10⁶ + 1,440 ≈ 2 × 10⁶ steps, against 2 × 10⁶ events sorted at ≈ 4 × 10⁷ comparisons. Roughly twenty times less work.

Merging returns [[1, 3]] for the input [[1, 10], [2, 3]]. What is the line, and what should it be?

The extend step assigns the new end instead of taking the maximum: it says out[-1][1] = e. It must be out[-1][1] = max(out[-1][1], e), because sorting by start says nothing about which interval ends last.