Insert Interval: Copy, Absorb, Copy in One Linear Pass

Insert interval looks like merge intervals with one extra element, and you can solve it exactly that way: append, sort, merge. That answer works and costs O(n log n). The question is really asking whether you notice that the list is already sorted and already disjoint, so the only unknown is where one block lands. Once you see that, the whole problem is three loops that together touch each interval once.

The problem it solves

You get a list of intervals sorted by start, none of them overlapping, and one new interval. Insert it so that the list stays sorted and disjoint, merging wherever the new interval overlaps existing ones.

For [1, 3], [6, 9], [12, 16] and a new interval [4, 8], the answer is [1, 3], [4, 9], [12, 16]: the new block overlaps [6, 9], so the two become one interval from the smaller start to the larger end. A new interval can overlap nothing, one interval, or a long run of them, and it can land before the first interval or after the last.

The intuition

Walk the sorted list once and put every existing interval into one of three groups:

• Strictly before. Its end is smaller than the new start. It cannot touch the new block, so copy it out unchanged.
• Touching. Its start is not greater than the new end. It overlaps the new block, so absorb it: the block becomes the smallest start and the largest end of the two. Keep absorbing while the next interval still touches the widened block.
• Strictly after. The first interval that starts past the new end, and everything after it. The list is sorted, so none of them can touch either. Copy them all in one go.

The groups appear in exactly that order because the input is sorted, which is why one forward scan is enough and no sort is needed. The widening matters: absorbing one interval can stretch the end far enough to reach the next one, and the loop checks against the current end, not the original one.

The one decision you have to make out loud is what "touching" means. With closed intervals, [1, 3] and [3, 5] share the point 3 and merge. With half-open intervals, such as meetings from 9:00 to 10:00 and from 10:00 to 11:00, they do not. The code differs by one comparison in each loop.

Watch it run

The animation uses the lesson's calendar. It starts from the booked list, already sorted and non-overlapping: 1–3, 6–9, 12–16. The block to insert is 4–8, and only its position is unknown, so no sort is needed. Pass one: 1–3 ends before 4 starts, so it is copied out untouched. Pass two: 6–9 starts at 6, inside the new block, so it gets absorbed. The block widens to the smallest start and the largest end of the two, and 4–8 becomes 4–9. Then 12–16 starts past 9, so the absorbing stops. Pass three emits the widened block and copies the tail straight across. Out comes 1–3, 4–9, 12–16: still sorted, still disjoint, in a single linear pass.

The code

The lesson's three passes as a function, for closed intervals:

def insert(intervals, new):
    out, i, n = [], 0, len(intervals)
    start, end = new
    while i < n and intervals[i][1] < start:     # ends before the new block starts
        out.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:      # touches the block: absorb it
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    out.append([start, end])
    out.extend(intervals[i:])                    # nothing after this can touch
    return out

print(insert([[1, 3], [6, 9], [12, 16]], [4, 8]))
# [[1, 3], [4, 9], [12, 16]]
print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
# [[1, 2], [3, 10], [12, 16]]
print(insert([], [5, 7]), insert([[4, 5]], [1, 2]))
# [[5, 7]] [[1, 2], [4, 5]]
print(insert([[1, 3]], [3, 5]))                  # [[1, 5]]

For half-open intervals, where an end point is not part of the interval, flip the two boundary comparisons so that touching end to start does not merge:

def insert_half_open(intervals, new):
    out, i, n = [], 0, len(intervals)
    start, end = new
    while i < n and intervals[i][1] <= start:    # ending exactly at start: no overlap
        out.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
    return out + [[start, end]] + intervals[i:]

print(insert_half_open([[1, 3]], [3, 5]))        # [[1, 3], [3, 5]]

Against the brute force, append then sort then merge, on 3,000 random calendars:

import random

def brute(intervals, new):
    merged = []
    for s, e in sorted(intervals + [new]):
        if merged and s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged

random.seed(18)
ok = True
for _ in range(3000):
    points = sorted(random.sample(range(40), 2 * random.randint(0, 6)))
    booked = [[points[k], points[k + 1]] for k in range(0, len(points), 2)]
    s = random.randint(0, 39)
    new = [s, random.randint(s, 42)]
    ok &= insert(booked, new) == brute(booked, new)
print(ok)                                        # True

The complexity

• Time: O(n). The three loops share one index that only moves forward, so each interval is examined once.
• Space: O(n) for the output list. Only the widened block is new; everything else is copied across.
• Binary search does not change the bound. You can find the first touching interval in O(log n), but building the returned list is still O(n). It only pays off in a structure that supports cheap inserts, such as a balanced tree keyed by start.
• The sort-and-merge approach is O(n log n), correct but it ignores what the input already gives you.

Where it goes wrong

• Comparing against the original end. After absorbing [3, 5], the block may reach [6, 7]. Use the widened end in the loop condition.
• The wrong boundary. < versus <= decides whether touching intervals merge. Ask which convention the problem uses.
• Forgetting the new block when nothing overlaps. It still has to be appended, between the two copied groups.
• Mutating the input. Widening an interval in place changes the caller's list; build the new block from local variables.
• Sorting anyway. It gives the right answer and signals that you did not use the precondition.

When it shows up in interviews

It usually comes right after merge intervals, as "now the list is already clean, can you do better than sorting?". The interviewer is listening for the O(n) observation and for how you handle the edges: the new interval before everything, after everything, swallowing every interval, or touching an end point exactly. Calendar-style follow-ups are common, such as booking a slot or finding free time, and they reuse the same before, touching and after split.

How to say it in an interview

"The input is sorted and disjoint, so I do not need to sort. I scan once. Every interval that ends before the new one starts goes straight to the output. Then every interval whose start is within the new block's end gets absorbed: I widen the block to the smaller start and the larger end, and keep going with the widened end. Then I append the block and copy the rest. That is O(n) time and O(n) for the output. I would confirm whether touching end points count as overlapping, because that changes one comparison."

The unsorted version is in merge intervals, and the same sweep over sorted endpoints counts rooms in meeting rooms II.