Intervals

Interval problems look varied and are almost all the same problem. Sort the intervals, walk them once, and compare each one against the single interval you are currently holding. The sort is what makes that comparison sufficient — without it you would have to check every pair.

Overlap, precisely#

Get this definition right and most of the difficulty disappears. Two intervals [a₁, a₂] and [b₁, b₂] overlap when:

a₁ <= b₂  and  b₁ <= a₂

Which is easier to remember by its negation: they do not overlap only when one ends before the other begins. There are just two ways to miss, and the condition above rules out both.

If the intervals are already sorted by start, so a₁ <= b₁, this collapses to a single comparison — b₁ <= a₂. That is the entire test used below, and the reason sorting comes first.

One question to settle before writing any code: are the endpoints inclusive? Whether [1, 2] and [2, 3] overlap is not a mathematical fact, it is a decision the problem makes. For meeting rooms they usually do not — one meeting can end exactly as the next begins — so the test becomes < rather than <=. Ask, or state your assumption.

Sort, then sweep#

Sorting by start time buys the invariant that makes one pass enough: every interval you have not looked at yet begins at or after the current one. So if the next interval does not overlap what you are holding, nothing later can either — you are finished with it and can emit it.

Watch which bar is being compared against which. Only ever two things are in play: the interval under the cursor and the one being accumulated. Everything already emitted is settled and never revisited.

sort intervals by start

cur = intervals[0]
out = empty list

for iv in intervals[1..]:
    if iv.start <= cur.end:          // they touch
        cur.end = max(cur.end, iv.end)
    else:                            // gap: cur can never grow again
        append cur to out
        cur = iv

append cur to out                    // the last one is still in hand
return out

Two details cause most of the bugs. max is required when extending — a short interval fully inside a long one must not shrink it. And the final append is easy to forget, because the loop ends while you are still holding an interval that has never been emitted.

Cost is O(n log n), and the sort is all of it; the sweep is linear.

Inserting into a sorted list#

Given intervals already sorted and non-overlapping, plus one new interval to add, the same sweep works in three phases:

1. Everything ending before the new interval starts — copy across untouched.
2. Everything overlapping it — absorb into the new interval, widening both ends.
3. Everything starting after it ends — copy across untouched.

Written that way it is O(n) with no sort at all, because the input was already ordered. The only subtlety is that phase 2 widens the start as well as the end: an existing interval may begin before the new one does.

Sorting by the other end#

Not every problem sorts by start. When you are choosing a maximum number of non-overlapping intervals — scheduling as many meetings as possible in one room — sort by end time instead and greedily take each interval that starts after the last one you accepted.

The reason is worth understanding rather than memorising: finishing earliest leaves the most room for everything after it. That is a genuine greedy argument, and it fails if you sort by start, because one early-starting, very long interval can block several short ones.

So the choice is: sort by start to combine, sort by end to select.

Counting overlaps#

When you need the maximum number of intervals active at once — how many rooms do these meetings need — stop thinking about intervals and think about events. Split each [s, e] into a +1 at s and a −1 at e, sort all the events by time, and sweep, tracking a running count. The peak of that count is the answer.

This is the sweep line, and it generalises well: the same event list answers “when was anything active”, “when were three or more active”, and similar questions that are awkward to phrase in terms of whole intervals.

Recognising it#

• The input is pairs of numbers representing ranges — times, positions, versions.
• You are asked to merge, insert, count overlaps, or find a conflict.
• The obvious solution compares every pair. Sorting nearly always replaces that with one pass.
• Before coding, decide two things: sort by start or end, and are endpoints inclusive. Getting either wrong produces code that is right on the examples and wrong at the boundaries.

Summary#

Sort first — that is the whole trick, and which key you sort by encodes what you are trying to do. After sorting, one pass and one held interval is enough, because the ordering guarantees nothing you have not seen can reach back. Merging combines what touches; selecting takes what ends soonest; counting turns intervals into events and watches a running total.