Merge Intervals

Given intervals as [start, end] pairs, merge every group that overlaps and return the result sorted by start. (LC 56)

This is the interval family's entry point, and it shows up inside bigger problems all the time: calendars, ranges of log lines, "which times are covered", and anything that says overlapping.

The recipe

Say before you type: "Overlap is easy to see once the intervals are sorted by start. After that, each interval either starts inside the last merged one, so I extend its end, or after it, so I start a new one."

1. Sort by start. This is the whole trick: after it, two intervals can only overlap if they are neighbours in the sweep.
2. Walk the sorted list, keeping the merged result.
3. If the current interval's start <= last.end, they overlap: set last.end = Math.max(last.end, end).
4. Otherwise push it as a new interval.

The code

function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // numeric, not text
  const merged: number[][] = [];

  for (const [start, end] of sorted) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end); // the new one may be INSIDE the last
    } else {
      merged.push([start, end]);
    }
  }

  return merged;
}

Why this shape

Without sorting you would compare every pair: O(n²), and a merge can cascade (a late interval can bridge two you already closed). Sorting by start removes the cascade. Everything that could still overlap the current interval is at the end of the merged list, so you only ever look at merged[merged.length - 1].

The Math.max matters because sorting by start says nothing about ends. [1,10] followed by [2,3] starts inside the first interval but ends well before it does, so copying the new end would shrink it.

Complexity

	Cost	Because
Time	O(n log n)	The sort dominates; the sweep is one pass
Space	O(n)	The result, plus the sorted copy

Traps

• Overwriting the end instead of taking the max. [[1,4],[2,3]] must stay [1,4]. This is the most common bug, and the first one to try.
• The default sort(). With no comparator, JavaScript sorts arrays as text, so [10,12] lands before [2,3]. Always pass (a, b) => a[0] - b[0].
• < versus <=. The problem says touching intervals merge, so [1,4] and [4,5] become [1,5]. That is <=. Ask which one the interviewer means, because the answer changes the code by one character.
• Merging adjacent integers. [1,2] and [3,4] are not touching on a continuous line. Only merge when start <= last.end, never last.end + 1, unless the problem is about whole-number ranges and says so.
• Mutating the input. Sorting in place changes the caller's array. Copy first, or say you are allowed to.

The pattern this trains

Sort, then make one pass that only looks at the previous item. The same shape solves Insert Interval (57), Non-overlapping Intervals (435, count what you have to drop), Meeting Rooms (252) and Meeting Rooms II (253, where the sweep keeps a heap of end times instead of one interval). When a prompt says "overlapping", "conflicting" or "covered", sort by start first and see what is left to do.