Merge Intervals

Medium

Sort by start, extend or append

Problem

Given an array of intervals, merge all overlapping intervals and return the non-overlapping result.

In simple words

Sort by start, then extend the current interval whenever the next one overlaps it.

The idea

After sorting by start time, walk the list extending the current interval whenever the next one begins before it ends, otherwise closing it and starting a new one. Sorting guarantees you only ever compare against the interval being built.

The trick

Extend with max(end) — the next interval may end earlier.
O(n log n) for the sort, O(n) for the merge.

←→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.