Merge Intervals Pattern

Why Intervals Become One Segment

Interval questions look different on the surface, but the important structure is always the same: each item claims a continuous stretch on a line. The line might be time, positions, bandwidth, seat usage, or numeric ranges. Once the data is sorted by start time, any interval that can overlap with the current answer must appear next to it. That one observation is what turns a messy pairwise-comparison problem into a clean single sweep.

Think of the current merged interval as the portion of the line you already understand. When the next interval starts before that known portion ends, the two intervals describe the same connected region, so you should widen the current region instead of storing a separate result. When the next interval starts after the current region ends, the connection is broken. At that moment, you know the current interval is finished forever and can safely append it to the answer.

This is why sorting matters so much. Without sorting, you cannot tell whether a future interval might sneak backward and overlap something you already emitted. After sorting, the future only moves right. That gives you a strong invariant: the only interval that can interact with your current merged segment is the next one in the ordered list. Interviews love this pattern because it rewards recognizing the geometry of the problem rather than memorizing a template.

A second mental model helps with variants like insert interval, meeting rooms, or interval intersections. Ask yourself what the running state represents. Sometimes it is a merged segment. Sometimes it is the number of simultaneous active meetings. Sometimes it is the overlap between two already-sorted lists. The pattern is still about ranges on a line, but the output changes: merge them, count them, discard them, or intersect them.

Step-by-Step Example

Use [[1,3],[2,6],[8,10],[9,12],[15,18]] as a worked example. The list is already sorted by start time, so begin with the first interval as your active region: [1,3]. The next interval is [2,6]. Its start value 2 is not beyond the current end 3, so both intervals touch the same stretch of the line. Merge them by extending the end to max(3,6) = 6, giving [1,6].

Now inspect [8,10]. Its start 8 is greater than the current end 6, so there is a gap. That means [1,6] is complete; nothing later can reach back far enough to change it. Append [1,6] to the answer and start a new active region with [8,10]. The next interval is [9,12]. Because 9 <= 10, it overlaps the active region, so widen [8,10] to [8,12].

Finally, [15,18] starts after 12, so [8,12] becomes final. Append it, reset the active region to [15,18], and finish the scan. After the loop, remember to append the last active interval because it never encountered a closing gap. The final answer is [[1,6],[8,12],[15,18]]. That last append is a classic interview bug: people handle gaps correctly inside the loop, then forget the unfinished interval still living in memory.

The same example also explains why the algorithm is optimal. Every interval is visited once after the sort. No merged interval is reopened after it is emitted. So the expensive part is sorting, not merging. In other words, the pattern is not about clever mutation; it is about establishing the right order so that a single pass becomes trustworthy.

Go Implementation

A clean Go solution keeps the active interval in two integers instead of repeatedly slicing and reallocating. That makes the invariant explicit: currentStart and currentEnd always describe the merged region formed by every interval seen since the last gap.

Notice that the overlap test uses start <= currentEnd, not start < currentEnd. Whether touching endpoints count as overlap depends on the problem statement. For Merge Intervals, [1,4] and [4,5] are merged because the ranges touch. In scheduling problems with strict separation rules, you may need start < currentEnd instead. The pattern stays the same, but the boundary condition changes the meaning of “collision.”

Recognizing Interval Variants

Reach for the interval pattern when each record has a start and end, and the question asks about overlap, free space, removal count, intersection, or simultaneous occupancy. If the input is unsorted, you often sort first. If there are two already-sorted lists, use two pointers instead of resorting. If the goal is maximum overlap at once, track start and end events instead of merged segments.

A useful interview sentence is: “I am modeling the line, not the array.” That signals that you understand why sorting helps. You are not sorting because interviews always start with sort.Slice; you are sorting because order on the array should match order on the underlying line. Once those two orders agree, the invariant becomes simple enough to reason about out loud.

Practice Problems

Quiz