Merge Intervals: The Sort-Then-Sweep Pattern Explained

Merge Intervals is less a problem than a template. Meeting rooms, calendar free time, inserting an interval, the total length covered by a set of ranges — they all start with the same two moves: sort by start, then sweep left to right holding one thing open. Learn why those two moves are enough and the whole family gets shorter.

The problem it solves

Given a list of intervals, combine every group that overlaps into one interval, and return the result. Three overlapping GPS windows at the same depot become one stay; two bookings that overlap become one busy block.

Without a strategy you compare every interval with every other one and merge pairs repeatedly until nothing changes. That is at least O(n²), and the "until nothing changes" loop is where bugs hide: merging A with B can create a block that now overlaps C, which you already checked.

The intuition

After sorting by start, one fact makes a single pass enough:

Once the next interval starts after the open block ends, nothing later can ever touch that block again.

Every later interval starts at least as late as this one — that is what sorting by start guarantees — so every later interval also starts after the block ends. The block is finished and can be written out for good.

So the sweep holds exactly one "open" block. For each next interval there are only two cases. If it starts at or before the open block's end, they overlap: stretch the end. If it starts after, there is clear air between them: close the block and open a new one.

The stretch uses max, not replacement. An interval can sit entirely inside the open block, like (2, 3) inside (1, 10), and replacing the end would shrink the block to 3.

Watch it run

Watch the single open block on the merged row. It stretches while the sorted spans keep starting inside it, and the first span that starts past its end closes it for good.

The key thing to notice is that closed blocks are never touched again. That is the one-pass guarantee made visible.

The code

def merge(intervals, touching=True):
    out = []
    for s, e in sorted(intervals):             # sort by start
        if out and (s <= out[-1][1] if touching else s < out[-1][1]):
            out[-1][1] = max(out[-1][1], e)    # overlap: stretch, never shrink
        else:
            out.append([s, e])                 # gap: open a new block
    return out

def merge_by_end(intervals):                   # the wrong sort key
    out = []
    for s, e in sorted(intervals, key=lambda iv: iv[1]):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

print(merge([(8, 10), (1, 3), (2, 6), (9, 11)]))   # [[1, 6], [8, 11]]
print(merge([(1, 10), (2, 3)]))                    # [[1, 10]]  nested
print(merge([(1, 2), (2, 3)]))                     # [[1, 3]]   closed: touching merges
print(merge([(1, 2), (2, 3)], touching=False))     # [[1, 2], [2, 3]]  half-open
print(merge([]))                                   # []
print(merge_by_end([(1, 2), (5, 6), (0, 10)]))     # [[1, 2], [5, 10]]  wrong

The "open block" is simply the last entry of out. There is no separate variable to keep in sync, and the empty-input case falls out naturally.

We also compared merge against a brute-force answer — mark every covered point, then read off the runs — on thousands of random interval sets, including duplicates, nested spans and zero-length ones. They matched every time.

Why the sort key matters

The last line is the instructive failure. Sorting by end looks equally reasonable and is wrong. (0, 10) has the largest end, so it comes last — after (1, 2) has already been closed as a finished block. The guarantee "nothing later can touch a closed block" depended on later intervals starting later, and sorting by end does not promise that.

Sorting by start is not a convenience; it is the proof.

The complexity

Time: O(n log n). The sort dominates. The sweep itself is O(n): each interval is looked at once and either stretches the open block or opens a new one.

Space: O(n) for the output, which in the worst case — no overlaps at all — is as large as the input. Python's sorted also makes a copy; sorting in place saves that if the caller does not need the original order.

If the intervals arrive already sorted, as they do in "insert interval", the sort disappears and the whole thing is O(n). That is the point of the insert interval variant: find where the new interval lands and sweep once.

Where it goes wrong

• Do touching intervals merge? (1, 2) and (2, 3) share the point 2. For closed intervals they overlap; for half-open ones like [9:00, 10:00) meetings they merely meet. Ask, then choose <= or <. The touching flag above is exactly that one character.
• Replacing the end instead of taking the max. Nested intervals shrink the block.
• Mutating the caller's data. Stretching out[-1][1] is safe here because out holds fresh lists. Stretch the input tuples or lists directly and the caller's intervals change underneath them.
• Comparing against the previous input interval instead of the open block. After a long interval, a later short one may start after the previous interval ends but still sit inside the open block.

The same sweep, other questions

Once the sort-then-sweep shape is familiar, variants are one-line changes to what happens at "stretch" and "close":

• Total covered length — sum e - s for each block as it closes.
• Can one person attend all meetings? Any stretch at all means an overlap; return false.
• Free time between meetings — the gaps between consecutive closed blocks.
• Minimum meeting rooms — a different sweep over start and end events, since overlaps must be counted rather than merged.

How to say it in an interview

"I sort by start time, which costs O(n log n). Then I sweep once, keeping the last merged interval as the open block. If the next interval starts at or before its end they overlap, so I extend the end to the max of the two ends — max, because the new one could be nested inside. Otherwise there is a gap, and because everything later starts even later, the open block can never be touched again, so I start a new one. Overall O(n log n) time, O(n) for the output. One question for you: should intervals that only touch at an endpoint merge?"

Ending with that question is not filler. It shows you know the one place where the specification, not the algorithm, decides the answer.