Insert Interval
Add one interval to a sorted list and merge what it touches, in three clean phases instead of one tangled loop
Problem Statement
You are given a list of non-overlapping intervals sorted by start time, and one new interval. Insert it, merging with anything it overlaps, and keep the result sorted and non-overlapping.
Input: intervals = [[1,3], [6,9]], new = [2,5]
Output: [[1,5], [6,9]]
[2,5] overlaps [1,3] → merged into [1,5]
Input: intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]], new = [4,8]
Output: [[1,2], [3,10], [12,16]]
[4,8] swallows [3,5], [6,7] and [8,10]Intuition
The lazy solution works: append the new interval, sort, and run Merge Intervals. That is O(n log n).
But the input is already sorted and already non-overlapping. Sorting again throws away a guarantee you were handed for free. With it, the answer is O(n).
The insight
The sorted list splits into exactly three regions relative to the new interval:
intervals: [1,2] [3,5] [6,7] [8,10] [12,16]
new: [4 ─────────── 8]
└ BEFORE ┘└─── OVERLAPPING ───┘ └ AFTER ┘
ends before touches starts after
new starts new new endsBefore — copy across untouched. Overlapping — absorb into one widened interval. After — copy across untouched.
Because the list is sorted, these regions are contiguous. You never go back.
Writing this as three separate loops is far clearer than one loop with a state flag — and it removes the class of bug where "am I still merging?" gets out of sync.
Approach
Phase 1 — copy everything that ends before the new interval starts
While intervals[i].end < new.start, this interval cannot touch the new one. Copy it and move on.
Phase 2 — absorb everything that overlaps
While intervals[i].start <= new.end, there is overlap. Widen the new interval to cover both:
new.start = min(new.start, intervals[i].start)
new.end = max(new.end, intervals[i].end)Then append the widened interval once, after the loop.
Phase 3 — copy the rest
Everything remaining starts after the new interval ends. Copy it across.
Solution
def insert(
intervals: list[list[int]], new_interval: list[int]
) -> list[list[int]]:
"""Insert an interval into a sorted, non-overlapping list.
Three phases: copy what ends too early, absorb what overlaps,
copy the rest. O(n) — the input's sorted order is reused.
"""
result: list[list[int]] = []
start, end = new_interval
i, n = 0, len(intervals)
# Phase 1 — entirely before the new interval.
while i < n and intervals[i][1] < start:
result.append(intervals[i])
i += 1
# Phase 2 — every overlapping interval widens the new one.
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
result.append([start, end])
# Phase 3 — entirely after.
while i < n:
result.append(intervals[i])
i += 1
return resultThe new interval is appended once, outside the loop
A common bug is appending inside phase 2, producing one copy per merge. The merged interval is a single result no matter how many originals it swallowed.
Appending after the loop also handles the case where phase 2 never runs — the new interval simply goes in at the right position, unmerged.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Time — i only ever moves forward, so all three loops together visit each interval once. Compare with the sort-and-merge approach at O(n log n).
Space — O(n) for the output. No extra structure.
Edge Cases
Related Problems
- Merge Intervals — the same merging when the input is not pre-sorted
- Non-overlapping Intervals — sorted by end, and greedy
- Merge Sorted Array — another problem solved by trusting sorted input