Merge Strategy

Merging is not about comparing every pair. Once intervals are sorted by start, you only need one active range called the current interval. It represents everything seen so far that belongs to the same connected block on the number line.

Start with the first interval as current. When the next interval overlaps it, the block is still connected, so extend the current end. When the next interval starts after current ends, the block is complete. Emit current, then begin a new block.

The closed-interval merge condition is next.start <= current.end. If true, the two ranges touch or overlap, so the merged block ends at max(current.end, next.end). For [1,3] followed by [2,6], carry [1,3], see 2 <= 3, and extend to [1,6].

If the condition is false, the next interval begins strictly after the carried range. For [1,6] followed by [8,10], 8 <= 6 is false, so [1,6] can never be affected by later intervals. Sorting guarantees every later start is at least 8, so it is safe to emit.

The invariant is that current is the merged result of all processed intervals that have not yet been emitted. Its start is the earliest start in that block, and its end is the farthest end seen among overlapping intervals in that block.

When the next interval overlaps, extending preserves the invariant because the block remains connected. When it does not overlap, no future interval can bridge the gap because starts are sorted. That gap proves the current block is final, which is why emitting is safe.

This exact structure powers more than the basic Merge Intervals problem. Insert Interval adds one new interval and then performs the same coalescing logic. Meeting-room variants use the same sorted boundaries but count conflicts instead of emitting merged ranges. Covered-interval and intersection problems also depend on tracking an active boundary correctly.

The reusable mental template is: sort by the boundary that makes the next decision local, carry the state that summarizes processed intervals, then either extend that state or finalize it. For module two, the boundary is usually start, and the carried state is the active merged interval.