Insert Interval
MediumCopy, absorb the overlaps, copy the rest
Problem
Given a sorted list of non-overlapping intervals and a new interval, insert it and merge any overlaps, returning the sorted result.
Copy intervals before the new one, merge all that overlap it, then copy the rest.
The idea
The list is already sorted and disjoint, so pass through it in three phases: intervals entirely before the new one, intervals overlapping it (which merge into one), and the rest. One linear pass, no sorting required.
The trick
- Overlap means `interval.start <= newEnd && newStart <= interval.end`.
- Merging takes min of starts and max of ends.
- O(n) because the input is already sorted.
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],[6,9]], newInterval = [2,5]
- Output:
- [[1, 5], [6, 9]]
- Explanation:
- [2,5] merges with [1,3] into [1,5].
Example 2
- Input:
- intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
- Output:
- [[1, 2], [3, 10], [12, 16]]
- Explanation:
- The new one swallows several.
Example 3
- Input:
- intervals = [], newInterval = [5,7]
- Output:
- [[5, 7]]
- Explanation:
- Nothing to merge with.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.