Insert Interval
Problem statement
You're given a list of intervals, intervals, that don't overlap each other
and are already sorted by their start value — think of them as existing
maintenance windows or deployment freezes on a shared calendar. You're also
given one more interval, newInterval, that needs to be added to that
calendar.
Two intervals overlap if they share even a single point in time (so [1, 3]
and [3, 5] count as overlapping, since they both touch 3).
Insert newInterval into intervals so the list stays sorted by start value
and still has no overlaps — merging any intervals that touch or overlap
newInterval into one combined interval. Return the resulting list. You
don't have to modify intervals in place; returning a new list is fine.
Examples
Example 1
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: newInterval = [2, 5] overlaps [1, 3] (they share the point 3), so they merge into [1, 5]. It doesn't touch [6, 9] at all, so that interval is unchanged.
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: [4, 8] overlaps [3, 5], [6, 7] and [8, 10] — it touches or crosses all three — so they merge together into one interval, [3, 10]. [1, 2] ends before 4, and [12, 16] starts after 10, so neither is touched.
Hints
newInterval: it ends before newInterval starts, it starts after newInterval ends, or it overlaps and needs merging.Approach
Optimal: Three-phase single pass
Intuition
intervals is already sorted and non-overlapping, so there's no need to sort
anything — that guarantee can be used directly. Split the work into three
phases in a single pass: first copy every interval that ends before
newInterval even starts straight into the result, since those can never
overlap it. Then, for as long as the next interval's start is still within
newInterval's current end, merge it in by growing newInterval's own start
and end to cover it — this sweeps up every overlapping interval in one go.
Once that stops, push the (possibly grown) newInterval into the result.
Finally, copy whatever intervals are left — they all start after
newInterval ends, so none of them can overlap it either.
Steps
- Start an empty result list, an index
i = 0, andstart, endset tonewInterval's own start and end. - While
i < nandintervals[i]'s end is beforestart: this interval can't overlapnewInterval— push it to the result and advancei. - While
i < nandintervals[i]'s start is ≤end: this interval overlaps — growstartto the smaller of the two starts andendto the larger of the two ends, then advancei. - Push the interval
[start, end](now covering everything it merged with) to the result. - While
i < n: these intervals all start afterend— push each one to the result as-is and advancei. - Return the result.
Dry run
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8],
start, end = 4, 8
| phase | i | interval | condition | action |
|---|---|---|---|---|
| before | 0 | [1,2] | 2 < 4 | push [1,2], i=1 |
| before | 1 | [3,5] | 5 < 4? no | stop "before" phase |
| merge | 1 | [3,5] | 3 ≤ 8 | start=min(4,3)=3, end=max(8,5)=8, i=2 |
| merge | 2 | [6,7] | 6 ≤ 8 | start=3, end=max(8,7)=8, i=3 |
| merge | 3 | [8,10] | 8 ≤ 8 | start=3, end=max(8,10)=10, i=4 |
| merge | 4 | [12,16] | 12 ≤ 10? no | stop "merge" phase → push [3,10] |
| after | 4 | [12,16] | — | push [12,16], i=5 |
Result: [[1,2],[3,10],[12,16]], matching Example 2.
Edge cases: an empty intervals list means both the "before" and "merge"
loops never run (n = 0), so the result is simply [newInterval]. If
newInterval starts after every existing interval ends, the "merge" loop
never runs either, and newInterval is pushed on its own after all the
existing intervals.
Complexity
Time O(n) - one pass through `intervals`, no sorting.
Space O(n) - for the output list; O(1) extra beyond that.
from typing import List
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
n = len(intervals)
result = []
i = 0
start, end = newInterval[0], newInterval[1]
while i < n and intervals[i][1] < start:
result.append(intervals[i])
i += 1
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])
while i < n:
result.append(intervals[i])
i += 1
return result
if __name__ == "__main__":
print(Solution().insert([[1, 3], [6, 9]], [2, 5])) # [[1, 5], [6, 9]]
print(Solution().insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])) # [[1, 2], [3, 10], [12, 16]]RecapThe whole problem in a few lines, for the night before
- Spot it: "insert one interval into an already-sorted, non-overlapping list and merge anything it touches"
- Idea: copy every interval fully before the new one, merge everything that overlaps it by growing the new interval's own bounds, then copy the rest — one linear pass, no sorting needed
- Cost: O(n) time, O(n) space for the output
- Trap: using
<instead of<=in the overlap check misses intervals that only touch at a shared endpoint, since the problem counts that as overlapping
Interview follow-ups
What if you needed to insert many new intervals, one after another?
Repeating this O(n) insert once per new interval costs O(n·m) total for m insertions. If all m new intervals are known upfront, it's usually cheaper to append all of them to the list, sort once — O((n+m) log(n+m)) — and merge everything in a single pass, trading away the "no sort needed" advantage of a single insert for the benefit of batching.
How would you support fast overlap checks on a huge, frequently-changing set of intervals?
Keep the intervals in a structure ordered by start that supports fast search and insert, such as a balanced tree or an interval tree, so a single insert or overlap query costs O(log n) instead of scanning the whole list. The trade-off is extra bookkeeping to keep that structure balanced as intervals are added and removed over time.
Frequently asked questions
Because intervals is already guaranteed sorted by start and non-overlapping — that's given in the problem, not something you have to establish. The brute-force approach only sorts because it throws that guarantee away and rebuilds the order from scratch, which is more general but wasted work here.
It means two intervals like [1, 3] and [3, 5] count as overlapping, not just touching, so both approaches use <= in their merge check (start <= current end, or intervals[i][0] <= end) rather than <. Using < instead would leave two intervals that only share an endpoint unmerged, which the problem doesn't allow.
It's the same shape as inserting a new maintenance window, deployment freeze, or resource reservation into an already-sorted schedule and merging it with anything it overlaps, so the calendar never ends up double-booked at any point in time.
The "before" and "after" phases would both do nothing — there's nothing that ends before newInterval starts, and nothing left over once the merge is done — while the merge phase would sweep through the whole list, and the result would be a single interval covering everything.
