Merge Overlapping Subintervals
MediumSort by start, extend or push
Problem
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input. You can return the intervals in any order.
Sort by start, then extend the current interval whenever the next one overlaps it.
The idea
Sort by start time and walk through: if the next interval begins before the current one ends, stretch the current end to cover it, otherwise close the current interval and start a new one. Sorting guarantees you only ever need to compare with the interval you are currently building.
The trick
- Sort by start; then a single pass suffices.
- Merge by taking max(end), not the new interval's end — it may be shorter.
- O(n log n) for the sort, O(n) for the merge.
Step 1 of 9. Four intervals on a 0–9 timeline: [1,3], [2,4], [6,8], [7,9]. Sort by start, then sweep.
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.
Constraints
- 1 <= intervals.length <= 10⁵
- 0 <= starti <= endi <= 10⁵
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.