Insert interval
We'll cover the following
A sorted list has no overlapping intervals. Insert a new interval and merge anything it overlaps.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
1-20
3-51
6-72
8-103
12-164
18-205
22-256
27-297
31-348
36-389
Insert 9-23 into a sorted list of non-overlapping intervals. Three phases: keep the ones before, merge the overlaps, keep the ones after.
new 9-23
1 / 13
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(n) | The list is already sorted: one pass in three phases. |
In Python
def insert(intervals, new):
res, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < new[0]: res.append(intervals[i]); i += 1
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]; i += 1
res.append(new)
return res + intervals[i:]Summary: say it in the interview
- Because the list is sorted, the work splits cleanly: skip everything that ends before the new interval, merge everything that overlaps it, then copy the rest. One pass, no sorting.
- Time O(n), space O(n). The list is already sorted: one pass in three phases.