Merge Intervals — The Shift Roster

Boss 2: The Shift Roster

Boss 1 got sorted, non-overlapping input as a gift and only had to slot one newcomer in. This boss gets no gifts. The input is a raw pile, so it earns the order with a sort, and the sweep that sort unlocks is THE canonical intervals move. Sort by start, walk left to right, keep one current block. The next four bosses are all remixes of the walk you're about to install.

The story

A cafe manager collects shift claims from the staff, handwritten scraps tossed into a jar all week: [[1,3],[2,6],[8,10],[15,18]]. She doesn't care who is working. She cares when the cafe is covered at all, so she needs the clean coverage roster.

She dumps the jar, sorts the scraps by start time, and stacks them into blocks:

sorted:  [1,3] [2,6] [8,10] [15,18]

[1,3]    first scrap            → open block [1,3]
[2,6]    starts at 2, block
         still runs until 3     → same stretch, block grows to [1,6]
[8,10]   starts at 8, block
         ended at 6             → gap! close [1,6], open [8,10]
[15,18]  starts at 15, past 10  → gap! close [8,10], open [15,18]

roster: [[1,6],[8,10],[15,18]]

The cafe is staffed from 1 to 6, from 8 to 10, from 15 to 18. Two scraps became one block, the gaps stayed gaps, and she only ever compared each scrap against the block in her hand.

The problem, dressed up properly

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

LeetCode 56.

The naive attempt

No order? Fine, compare everything with everything, merge any overlapping pair, repeat until nothing changes:

def merge(intervals):
    intervals = [list(iv) for iv in intervals]
    changed = True
    while changed:
        changed = False
        for i in range(len(intervals)):
            for j in range(i + 1, len(intervals)):
                a, b = intervals[i], intervals[j]
                if a[0] <= b[1] and b[0] <= a[1]:    # Boss 1's overlap test
                    intervals[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    intervals.pop(j)
                    changed = True
                    break
            if changed:
                break
    return sorted(intervals)

Every pass is O(n²) pair checks, a merge can create new overlaps that need another pass, and the whole thing grinds toward O(n³) in bad cases. The real crime is philosophical, though: without order, any scrap might overlap any other, so you're forced to check all pairs. Order is exactly what kills that.

The weapon: sort, then sweep

Sort by start time and something lovely happens: all the intervals that could possibly merge with your current block become neighbors. Once the next interval starts past the block's end, no later interval can reach back (their starts are even bigger), so the block is finished forever. Overlap checking collapses from all-pairs to a one-liner against the previous block only.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda iv: iv[0])         # the move that unlocks everything
    merged = [intervals[0]]                      # current block sits at merged[-1]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:               # starts at or before block's end: overlap
            merged[-1][1] = max(merged[-1][1], end)   # extend (max guards nested intervals)
        else:                                    # gap: block is final
            merged.append([start, end])          # open a new block
    return merged

That's the whole boss. Note the invariant the sweep maintains: everything in merged before the last block is final, untouchable, done. Only the last block is still alive. That "only the frontier is mutable" shape is the master key you'll keep turning for the rest of this dungeon.

Watching it work

[[1,3],[2,6],[8,10],[15,18]], already sorted by start:

open block [1,3]                     merged [[1,3]]
[2,6]:   2 at most 3  → extend       merged [[1,6]]     (end = max(3,6))
[8,10]:  8 past 6     → new block    merged [[1,6],[8,10]]
[15,18]: 15 past 10   → new block    merged [[1,6],[8,10],[15,18]]

roster [[1,6],[8,10],[15,18]] ✓

Same roster the manager stacked by hand, one comparison per scrap.

Gotchas

1. Skipping the sort. On unsorted input the sweep's whole logic is void, an early interval can overlap a late one and the one-block comparison never sees it. The sort isn't preprocessing, it is half the algorithm.

2. Extending with end instead of max. Try [[1,10],[2,3]]: the block is [1,10], the next interval is nested inside it. Write merged[-1][1] = end and the block shrinks to [1,3]. Sorting by start says nothing about ends, so nested intervals are always lurking. Always max.

3. Comparing against the current interval instead of the block. The check is start <= merged[-1][1], the growing block's end, not the previous raw interval's end. With [[1,6],[2,3],[4,5]], comparing [4,5] against [2,3] reports a gap that the block [1,6] says doesn't exist.

4. Endpoint fine print, again. Here start <= merged[-1][1] merges touching intervals like [1,2] and [2,3], same convention as Boss 1. Boss 3 flips it. Two characters of code, opposite answers.

5. Sorting by end, or by both. Only the start matters for the sweep's correctness. Sorting by end breaks the "no later interval can reach back" argument, and fancy multi-key sorts add nothing here but bugs.

Complexity

The sort dominates; the sweep after it is one O(n) pass with O(1) work per interval.

Time: O(n log n). Space: O(n) for the output (sorting in place, O(log n) extra otherwise).

Boss down. XP gained.

The manager pins three clean blocks to the corkboard, tosses the jar of scraps, and never once asked who claimed what.

What you walked away with:

• Sort-then-sweep, the dungeon's master key: sort by start, keep one live block, extend or close
• The frontier invariant: every block behind the current one is final, so each interval is compared against exactly one thing
• Sorting by start is what turns overlap detection from all-pairs O(n²) into a one-liner
• max on the block's end, because nested intervals don't care how you sorted

Next up: Boss 3 — The Overbooked Stage. A festival stage with too many acts: cancel the fewest bookings so nothing overlaps, and the greedy choice of who survives is sneakier than it looks.