LeetCode 56 · Sorting · Greedy

Merge Intervals

MediumCombine every group of overlapping ranges into single intervals.
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping intervals that cover all the input ranges.

Walkthrough

try:
1
function merge(intervals) {
◄
2
  intervals.sort((a, b) => a[0] - b[0]);
3
  const res = [];
4
  let cur = intervals[0];
5
  for (let i = 1; i < intervals.length; i++) {
6
    const next = intervals[i];
7
    if (next[0] <= cur[1])        // overlap
8
      cur[1] = Math.max(cur[1], next[1]);
9
    else {                        // gap
10
      res.push(cur);
11
      cur = next;
12
    }
13
  }
14
  res.push(cur);
15
  return res;
16
}
—
1,32,68,1015,18MERGED118
cur (running)next (comparing)saved / mergedpending
STEP 0 / 12 · line 1
Start
Plan: sort the intervals by their start value, then sweep left → right, growing one running interval and saving it whenever a gap appears.

Intuition

Picture each interval as a bar on a number line. Two bars overlap when one starts before the other ends — and merging them just means taking one bar from the earliest start to the latest end.

The key trick is to sort by start first. Once sorted, any intervals that overlap are guaranteed to be neighbours, so you never have to look backwards — you only compare each interval with the single "current" interval you are building.

Walk through the sorted list keeping one running interval, cur. For the next interval: if it starts at or before cur.end, it overlaps, so absorb it by pushing cur.end out to the larger of the two ends.

If it starts after cur.end, there is a gap — cur is finished and can never grow again, so save it and let the next interval become the new cur.

Why max(cur.end, next.end)? Because next might be completely inside cur (e.g. [1,10] then [2,3]); taking the max keeps the longer reach instead of shrinking it.

The algorithm

  1. 01Sort the intervals by their start value.
  2. 02Set cur = the first interval.
  3. 03For each remaining interval next: if next.start ≤ cur.end, they overlap → set cur.end = max(cur.end, next.end).
  4. 04Otherwise there is a gap → push cur to the result, then set cur = next.
  5. 05After the loop, push the final cur. That list is the answer.

Reference implementation

1
function merge(intervals) {
2
  if (intervals.length === 0) return [];
3
  intervals.sort((a, b) => a[0] - b[0]);
4
  const res = [];
5
  let cur = intervals[0];
6
  for (let i = 1; i < intervals.length; i++) {
7
    const next = intervals[i];
8
    if (next[0] <= cur[1]) {          // overlap
9
      cur[1] = Math.max(cur[1], next[1]);
10
    } else {                          // gap
11
      res.push(cur);
12
      cur = next;
13
    }
14
  }
15
  res.push(cur);
16
  return res;
17
}

Complexity

Time
O(n log n) — the sort dominates; the single sweep afterwards is O(n).
Space
O(n) for the output list (O(log n)–O(n) for the sort itself).