Insert Interval
Given a sorted list of non-overlapping intervals and a new interval, insert it and merge where necessary, returning the result still sorted and non-overlapping.
- 0 <= intervals.length <= 10⁴
- intervals[i].length == 2
- 0 <= starti <= endi <= 10⁵
- intervals is sorted by starti in ascending order.
- newInterval.length == 2
- 0 <= start <= end <= 10⁵
Intuition
Insert interval adds a new interval to a list already sorted by start time and non-overlapping, merging where necessary. That the input is already sorted and clean is the advantage to exploit — no sorting is needed, and one pass suffices.
The intervals divide naturally into three groups relative to the new one:
- Those ending before it starts, those overlapping it, and those starting after it ends.
The first and third groups are copied unchanged. Only the middle group merges, and merging is straightforward: the combined interval takes the minimum start and maximum end across the new interval and everything it touches.
So the algorithm walks the list once. While an interval ends before the new one starts, append it. Then, while an interval starts at or before the new one ends, absorb it by widening the bounds. Finally append the merged interval and copy the rest.
The overlap test is where solutions go wrong. Intervals touching at a point — [1, 3] and [3, 5] — do overlap for this problem and merge into [1, 5]. So the comparisons must be <= and >= rather than strict, or touching intervals are left separate.
The merged interval must be appended after the absorbing loop finishes, not inside it. Appending during the loop emits partially merged intervals.
Two boundary cases fall out with no special handling: a new interval before everything is appended first because the first loop never runs, and one after everything is appended last because the second loop never runs.
The input is already sorted, so three sequential passes suffice: copy everything strictly left of the new interval, absorb everything that touches it, then copy the rest. No sorting, no re-merging — the ordering does the work.
Approach
Before reading on: price up what enumerating every case costs here, then ask what sorting by one endpoint makes obvious that was hidden before. Aim for O(n) time and O(n) space.
Use the existing sort
The input is already sorted and non-overlapping, so no sorting is needed — a single left-to-right pass handles everything.
Split into three groups
Intervals either end before the new one starts, overlap it, or start after it ends. Only the middle group requires any work.
Copy the intervals before
While an interval ends before the new one starts, append it unchanged. These cannot be affected by the insertion.
Absorb the overlapping ones
While an interval starts at or before the new one ends, widen the bounds to the minimum start and maximum end across everything touched.
Treat touching as overlapping
[1, 3] and [3, 5] merge into [1, 5]. Use <= and >= rather than strict comparisons, or touching intervals are wrongly left separate.
Append the merged interval once
Add the widened interval after the absorbing loop ends, not inside it. Appending during the loop emits partially merged results.
Cost of the pass
Each interval is examined once, giving O(n) time and O(n) space for the output. The boundary cases need no special handling — the loops simply do not run.
Solution & live demo
Common pitfalls
Using < for the overlap test
while i < n and intervals[i][0] < hi:
while i < n and intervals[i][0] <= hi:
Touching intervals like [1,3] and [3,5] must merge into [1,5]. The strict comparison treats them as disjoint and emits two adjacent intervals where one is expected.
Re-sorting and running the general merge
intervals.append(newInterval) intervals.sort() # merge all
while i < n and intervals[i][1] < newInterval[0]:
Correct but O(n log n) on already-sorted data. The three-phase walk is linear because it exploits the guarantee the problem hands you.
Not extending lo downward
hi = max(hi, intervals[i][1])
lo = min(lo, intervals[i][0]) hi = max(hi, intervals[i][1])
The first overlapping interval may start before the new one — inserting [4,8] into a list containing [3,5] yields [3,8]. Only tracking the upper bound truncates the merged result's left edge.
Edge cases
Both loops skip and the new interval is the entire answer.
Phase one copies nothing, phase two merges nothing, so it is placed first and the rest follow.
Phase one copies all, and the new interval lands at the end.
Phase two runs repeatedly, collapsing all of them into one block — the reason hi uses a running max.