Merge Intervals

Medium

Problem

Given a list of intervals [start, end], merge every group of overlapping intervals and return the resulting non-overlapping intervals, sorted by start. Intervals that touch (one ends where the next starts) count as overlapping.

Example 1

Input:  [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]

[1,3] and [2,6] overlap, so they merge into [1,6].

Example 2

Input:  [[1,4], [4,5]]
Output: [[1,5]]

Also asked as: Merge Overlapping Intervals

Test cases

Case 1

Input:    [[1,3],[2,6],[8,10],[15,18]]
Expected: [[1,6],[8,10],[15,18]]

Case 2

Input:    [[1,4],[4,5]]
Expected: [[1,5]]

Case 3

Input:    [[1,4],[0,4]]
Expected: [[0,4]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort by start, then sweep

Time O(n log n)Space O(n)

After sorting, an interval either extends the last merged one (overlap) or starts a new one.

function merge(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const res = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = res[res.length - 1];
if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
else res.push(intervals[i]);
}
return res;
}