Insert Interval

Insert Interval takes a list of intervals that is already sorted and non-overlapping, and asks you to slot one new interval into it — merging anything it touches. It is the classic sweep over sorted intervals problem, and the structure is cleaner than it first looks.

The slow way first

You could throw all the intervals plus the new one into a list, sort by start, and run a general "merge intervals" pass. That works, but it pays O(n log n) for a sort you do not need — the input is already sorted. We can do the whole thing in one linear sweep.

The question to ask: since the list is sorted, where does the new interval fit, and which neighbors does it touch? Everything splits into three clean groups along the timeline.

The idea: append, merge, append

Walk the sorted list once and bucket every interval into three phases:

1. Before — intervals that end before the new one starts. They cannot overlap, so copy them straight into the result.
2. Overlapping — intervals that start at or before the new interval ends. Fold each into the new interval by stretching its bounds: new = [min(starts), max(ends)]. On the canvas this is the orange bar growing to cover them.
3. After — everything left. They start past the merged interval, so copy them straight in.

Because the input is sorted, these three groups appear in exactly that order — no sorting, no second pass.

Walk through it

Step through the animation. The orange bar is the new interval [4,8]. First [1,2] lands in the result untouched. Then [3,5], [6,7], and [8,10] each overlap, so the orange bar stretches — first left to 3, then right to 10. Once nothing overlaps, the merged bar [3,10] drops into the result and we are done.

Pseudocode

result = empty list
i = 0
# phase 1: intervals that end before new starts
while i < n and intervals[i].end < new.start:
    append intervals[i] to result
    i += 1
# phase 2: merge everything that overlaps new
while i < n and intervals[i].start <= new.end:
    new.start = min(new.start, intervals[i].start)
    new.end   = max(new.end,   intervals[i].end)
    i += 1
append new to result
# phase 3: the remaining intervals
while i < n:
    append intervals[i] to result
    i += 1
return result

The Python solution

def insert(intervals, new):
    result = []
    i, n = 0, len(intervals)
    # phase 1: intervals strictly before new
    while i < n and intervals[i][1] < new[0]:
        result.append(intervals[i])
        i += 1
    # phase 2: merge every overlapping interval
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    result.append(new)
    # phase 3: intervals strictly after new
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

• Phase 1 copies intervals whose end is strictly less than the new start — they sit entirely to the left.
• Phase 2 is the heart: an interval overlaps when its start is <= new.end. We absorb it by taking the min of starts and the max of ends, which is the orange bar growing on the canvas.
• After the merge loop, result.append(new) drops the grown interval into place — it is now correctly ordered.
• Phase 3 copies whatever is left; those intervals all start past the merged bar, so order is preserved.

Complexity

Each interval is looked at once across the three loops, so the sweep is O(n). The space is O(n) for the output list (or O(1) extra if you do not count the result).

When this pattern shows up

Practice