Merge Intervals

Medium

Sort by start · extend while overlapping

In simple words

Sort by start, then join any two ranges that touch or overlap into one.

The idea

Sort by start. Walk through, and whenever the current interval overlaps the last merged one, stretch that one's end; otherwise start a new merged interval.

←→stepspaceplay

1/9

Optimal

timeO(n log n)spaceO(n)

Grow the running interval.

1intervals.sort((a,b)=>a[0]-b[0]);2const out = [intervals[0]];3for (const [s, e] of intervals.slice(1)) {4  const last = out.at(-1);5  if (s <= last[1]) last[1] = Math.max(last[1], e);6  else out.push([s, e]);7}

Input

grid: 4 × 10

Memory

cells marked: 12
groups: —

Output

merged end: —
result: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output:: [[1, 6], [8, 10], [15, 18]]
Explanation:: [1,3] and [2,6] overlap into [1,6].

Example 2

Input:: intervals = [[1,4],[4,5]]
Output:: [[1, 5]]
Explanation:: Touching ends merge into [1,5].

Example 3

Input:: intervals = [[1,2],[3,4]]
Output:: [[1, 2], [3, 4]]
Explanation:: No overlap → both stay.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.