Problem Understanding
Each intervals[i] is a range [start, end]. Combine every group of overlapping ranges into one range and return the result: a list in which no two ranges overlap and every original range is still covered.
Example:
- Input:
[[1,3],[2,6],[8,10],[15,18]] - Output:
[[1,6],[8,10],[15,18]] - Explanation:
[1,3]and[2,6]share the stretch from 2 to 3, so they become the single range[1,6].
Algorithm Strategy
- Sort the Intervals: First, sort the intervals based on their start times. This brings potentially overlapping intervals next to each other.
- Iterate and Merge: Create a
mergedlist and add the first interval. - Compare: For each subsequent interval, check if it overlaps with the last interval in the
mergedlist (i.e.,current.start <= last.end). - Update: If they overlap, update the last interval's end time to
max(last.end, current.end). If they don't, simply append the current interval to themergedlist.
Interactive Visualization
4 INTERVALS
INPUT
intervals · as given
[1,3]
[2,6]
[8,10]
[15,18]
1
18
merged · 0
1
18
Read
—
Last end
—
Merged
0
merged
Empty
Merge 4 intervals
Next
Sort by start — already in order: [[1,3], [2,6], [8,10], [15,18]]
Intervals
Legend & Complexity
The interval being merged, tagged “current”
The last interval in merged, tagged “last”, when it is compared
Already in merged: “appended” or “merged”
The returned intervals
Time
O(n log n)
Space
O(n)
Observe how sorting simplifies the problem to a linear merge process.
Dry Run
Input: [[1,3], [2,6], [8,10], [15,18]]
The code appends when merged is empty or its last interval ends before the current one starts (last end < start); otherwise it extends that last interval.
| Step | Current | last end < start? |
Action | merged |
|---|---|---|---|---|
| Init | - | - | Sort by start: [[1,3], [2,6], [8,10], [15,18]] |
[] |
| 1 | [1,3] |
merged is empty | Append | [[1,3]] |
| 2 | [2,6] |
3 < 2? No — overlap |
End = max(3, 6) = 6 |
[[1,6]] |
| 3 | [8,10] |
6 < 8? Yes |
Append | [[1,6], [8,10]] |
| 4 | [15,18] |
10 < 15? Yes |
Append | [[1,6], [8,10], [15,18]] |
Edge Cases & Common Mistakes
- Empty Input: Handle
[]input gracefully. - Single Interval: Don't crash on inputs like
[[1,4]]. - Completely Contained:
[[1,10], [2,5]]-> Merge logicmax(10, 5) = 10handles this. - Touching:
[[1,2], [2,3]]->2 <= 2, so they merge into[1,3].
Solution
Optimal solution using O(N log N) sorting.
Merge Intervals Code
1var merge = function(intervals) {2 intervals.sort((a, b) => a[0] - b[0]);3 const merged = [];4 for (const interval of intervals) {5 if (!merged.length || merged[merged.length - 1][1] < interval[0]) {6 merged.push(interval);7 } else {8 merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);9 }10 }11 return merged;12};
More practice: DSA interview questions with answers · patterns cheat sheet