Intervals

The question

You are given a list of pairs, each a start and an end. Merge the ones that overlap. Or: pick the most that do not overlap. Or: slot a new one in. Or: how many are running at once. Different words, one pattern.

Explain it to a ten-year-old

Your friends each tell you when they are at the park, like “two till six” and “one till three”. Written down in the order they told you, it is a mess. Line them up by when each one arrives and it becomes easy. Walk along the day. If the next friend arrives before the current group has left, they join the group and the group stays until the last of them leaves. If the next friend arrives after everyone has gone, that is a new group. At the end you know exactly when the park had someone in it.

The trick

Sort. Unsorted intervals can overlap anything, so every check is against everything, n squared. Sorted by start, an interval can only overlap the one you are currently holding, so one pass does it. The check is one comparison: does the next one start before the current one ends?

The second trick is knowing which end to sort by. Sort by start when you are merging or inserting, because you build the answer left to right. Sort by end when you are choosing the most that fit, because taking the one that finishes earliest leaves the most room for the rest. Getting the sort wrong is the most common mistake in the whole family.

The steps

Merge, sorted by start:

1. Sort by start.
2. out = [first].
3. For each interval after that: if its start is less than the end of out[-1], stretch out[-1].end to the max of the two ends. Otherwise append it.

def merge(intervals):
    intervals.sort()
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s < out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

Pick the most that do not overlap, sorted by end:

1. Sort by end.
2. last_end = -infinity, kept = 0.
3. For each interval: if its start is at or after last_end, keep it and set last_end to its end. Otherwise skip it.

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    last_end, kept = float("-inf"), 0
    for s, e in intervals:
        if s >= last_end:
            kept += 1
            last_end = e
    return kept          # removals needed = len(intervals) - kept

Both are O(n log n) for the sort and O(n) for the walk. Touching ends: decide whether [1, 3] and [3, 5] overlap before you write the comparison. The problem statement tells you. Most say they do not, so the check is a strict less-than.

The template

Somebody worked this out long ago, and the reason to memorise it is that every interval problem is the same eight lines with two decisions swapped. Learn the shape and the decisions, and Insert Interval, Non-overlapping Intervals and Burst Balloons stop being new problems.

intervals.sort(key=SORT_KEY)           # DECISION 1: by start to build, by end to choose
current = None
for s, e in intervals:
    if current is not None and s < current[1]:   # DECISION 2: overlap test, < or <=
        MERGE_OR_SKIP(current, s, e)   # build: stretch current.end = max(...). choose: skip
    else:
        EMIT(current); current = [s, e]  # a gap: close the old one, open a new one
EMIT(current)

The two decisions:

• Sort key. Start when the answer is a set of ranges you build left to right: merge, insert, free time. End when the answer is a count of ranges you choose: most meetings you can attend, fewest to remove, fewest arrows.
• On overlap. Build problems stretch the current interval. Choose problems throw the newcomer away, because the one you already hold ends sooner.

When the question is “how many at once”, the shape changes: split every interval into a start event and an end event, sort the events, and count up and down as you walk. That is the meeting rooms lesson, and the heap there is doing the same walk.

The part to understand rather than memorise is why sorting by end is safe for choosing. Among all the intervals that could be first, the one that ends earliest can never block more of the rest than any other choice would. Say that sentence to yourself until it is obvious. Then you can defend the greedy answer instead of just producing it.

In GPU infrastructure

Maintenance windows, burn-in reservations and job leases are all intervals on a rack. Merge them to see when a rack is actually free. Sort by end to schedule the most burn-in runs into a night. Turn them into start and end events and count up and down to know the most nodes ever busy at once, which is how you size the bastions. Employee Free Time is literally “when is every node in this pod idle so I can update the firmware”.

What I am listening for

• Whether you sort before you do anything else. If you start comparing every pair, I wait a minute and then ask what sorting would buy you.
• Which key you sort by, and whether you can say why. “By start” without a reason is a memorised answer. “By end because it frees up the most room” is understanding.
• The overlap test on touching ends. I ask whether [1, 3] and [3, 5] merge. I want you to ask me back.
• Whether you notice that out[-1] changes as you go. The stretch must use the max of both ends, not just the newcomer’s end. [1, 10] then [2, 3] is the trap.

Where it leads

All of these are the template with the two decisions made:

• Meeting Rooms. Sort by start, return false on the first overlap. The warm-up.
• Merge Intervals. The build shape, exactly as above. On LeetCode.
• Insert Interval. Already sorted. Copy the ones that end before it, merge the ones that overlap it, copy the rest.
• Non-overlapping Intervals. The choose shape, sorted by end. Answer is total minus kept.
• Minimum Number of Arrows to Burst Balloons. The choose shape again, wearing a costume.
• Interval List Intersections. Two sorted lists, two pointers, the overlap of each pair is max of starts to min of ends.
• Meeting Rooms II. How many at once. The event walk or the heap. On LeetCode.
• Employee Free Time. Merge everyone’s busy time, then the gaps between merged intervals are the answer.

Go deeper

• Intervals overview on Hello Interview is the source for the two-sort idea and the problem list.
• Merge Intervals walked through by NeetCode, and the interval branch of the NeetCode roadmap for the rest.
• Interval problems on LeetCode, the tag page. Do Merge, Insert and Non-overlapping in one sitting and you will see the template.
• Interval scheduling on Wikipedia has the proof that earliest-end-first is optimal, for the day an interviewer asks you to justify it.

With AI on the table. The assistant merges perfectly. I change the problem to “fewest to remove” and watch whether you notice the sort key must change. Then I hand it [1, 10], [2, 3], [4, 5] and ask what its merge returns. If it wrote out[-1][1] = e instead of the max, the answer is wrong, and the job is to see that in the code it gave you, not to run it.