Merge Intervals

Merge Intervals fuses overlapping ranges — like combining busy slots on a calendar — into the fewest possible blocks. The key move is to sort the intervals by start time first. Once sorted, any overlap can only be with the block you're currently holding, never with something already finalized behind you. That means a single left-to-right sweep is enough.

Why sorting by start makes it a single sweep

After sorting, each interval starts no earlier than the one before it. So when you look at the next interval, the only block it could possibly overlap is the one you're currently building — everything further back ended earlier and is out of reach. You never have to look backward.

The steps

1. 1Sort the intervals by their start value.
2. 2Start the output with the first interval as the current block.
3. 3For each next interval [s, e]: if s <= curEnd, extend — set curEnd = max(curEnd, e).
4. 4Otherwise there's a gap — emit the current block and start a new one at [s, e].
5. 5After the sweep, emit the final block.

Worked trace — [[1,3], [2,6], [8,10], [15,18]]

1. 1Already sorted by start. Current block = [1, 3].
2. 2Next [2, 6]: 2 <= 3 → overlap. Extend end to max(3, 6) = 6. Block = [1, 6].
3. 3Next [8, 10]: 8 > 6 → gap. Emit [1, 6]. New block = [8, 10].
4. 4Next [15, 18]: 15 > 10 → gap. Emit [8, 10]. New block = [15, 18].
5. 5End of sweep. Emit [15, 18]. Result: [[1, 6], [8, 10], [15, 18]].

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]); // by start
  const out = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const cur = out[out.length - 1];
    const [s, e] = intervals[i];
    if (s <= cur[1]) cur[1] = Math.max(cur[1], e); // overlap -> extend
    else out.push([s, e]);                          // gap -> new block
  }
  return out;
}