Mid · Sorting & intervals

Merge Overlapping Intervals

Merge closed numeric intervals [start, end], where start <= end. Touching endpoints overlap. Return intervals sorted by start and do not mutate any input array.

Examples

[[1,3],[2,6],[8,10]] → [[1,6],[8,10]]

Compare approaches

Repeated pair merging

Merge any overlapping pair, restart the search, then sort the survivors.

Time: O(n³) upper bound · Space: O(n)

function mergeIntervals(intervals) { const result = intervals.map(x => [...x]); let changed = true; while (changed) { changed = false; outer: for (let i = 0; i < result.length; i++) for (let j = i + 1; j < result.length; j++) if (result[i][0] <= result[j][1] && result[j][0] <= result[i][1]) { result[i] = [Math.min(result[i][0], result[j][0]), Math.max(result[i][1], result[j][1])]; result.splice(j, 1); changed = true; break outer; } } return result.sort((a,b) => a[0]-b[0]); }

Sort then sweep

After sorting, only the last merged interval can overlap the next one. Copy each pair to preserve the input.

Time: O(n log n) · Space: O(n)

function mergeIntervals(intervals) {
  const sorted = intervals.map(x => [...x]).sort((a,b) => a[0] - b[0]);
  const result = [];
  for (const interval of sorted) {
    const last = result[result.length - 1];
    if (last && interval[0] <= last[1]) last[1] = Math.max(last[1], interval[1]);
    else result.push(interval);
  }
  return result;
}

Common traps

Copying only the outer array still shares the inner pairs.
Use a numeric sort comparator.

Practise in the workspace →