Merge Intervals
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]]
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;}