56. Merge Intervals

Merge all overlapping intervals and return the non-overlapping intervals that cover every input interval.

After sorting by start, overlapping intervals are adjacent. Extend the last merged interval while the next one starts inside it.

1function merge(intervals: number[][]): number[][] {
2  intervals.sort((a, b) => a[0] - b[0]);
3  const res = [intervals[0]];
4  for (const [s, e] of intervals.slice(1)) {
5    const last = res[res.length - 1];
6    if (s <= last[1]) last[1] = Math.max(last[1], e);
7    else res.push([s, e]);
8  }
9  return res;
10}

sorted input

[1,3]

[2,6]

[8,10]

[9,12]

[15,18]

118

merged

[1,3]

Sort by start.

1 / 0

Space: play/pause · ←/→: step