Insert Interval

Problem

You have a list of non-overlapping intervals already sorted by start time, and a new interval to add. Insert it, merging with any intervals it overlaps, and return the resulting sorted, non-overlapping list.

My notes

Signal

Inserting into an already-sorted, already-merged list is a single linear sweep, not a full re-sort-and-merge — the moment you see "the input is already sorted and non-overlapping," that guarantee is there to be used.

Approach

Walk the existing intervals in three phases: first, copy over every interval that ends strictly before the new one starts (no overlap possible yet). Then, absorb every interval that overlaps the new one by expanding the new interval's start to the min and its end to the max, until you reach one that starts after the new interval ends. Append the (possibly expanded) new interval, then copy the rest unchanged.

Skeleton

result = []
i = 0
add all intervals ending before new.start unchanged
while current interval overlaps new: expand new to cover it, advance i
add expanded new interval
add all remaining intervals unchanged

Solution

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    result = []
    i, n = 0, len(intervals)
    start, end = new_interval

    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

Complexity

O(n) time — one pass over the input, each interval visited once. O(n) space for the result.

Pitfalls

Re-sorting and running general interval-merge on the whole list works but throws away the fact that the input was already sorted — costs an unnecessary O(n log n).
The overlap condition is intervals[i][0] <= end, not < — intervals that touch at an endpoint (e.g. [1,3] and [3,5]) still count as overlapping and must merge.
Forgetting to keep expanding end across multiple overlapping intervals — the new interval can absorb more than one existing interval in a row.