Insert Interval — The Calendar Slot

Welcome to Dungeon 13

Dungeon 12 signed off with a warning: calendars, meeting rooms, bookings that collide at 2 p.m. and pretend they don't. It promised that nearly every boss in here falls to one opening move, sort by start time and sweep, and that the rest is deciding what to do when two intervals overlap. That's this dungeon. Six bosses, the shortest run so far, and the patterns inside carry entire products: calendar apps, room booking systems, CPU schedulers, all of them are interval problems wearing a suit.

The machine: one overlap test

An interval is just a pair, [start, end]. A meeting from 1 to 3. A shift from 6 to 9. That's the whole data structure, and the whole dungeon runs on one question: do two of them overlap?

Two intervals overlap when a.start is at most b.end and b.start is at most a.end. Flip it around and it's even simpler: they do not overlap only when one ends before the other begins. Three cases, and only the outer two are safe:

disjoint, a left:    a: [1,3]
                     b:          [6,9]      a ends before b begins → no overlap

overlapping:         a: [1,3]
                     b:    [2,5]            they share 2..3 → overlap

disjoint, a right:   a:          [6,9]
                     b: [1,3]               b ends before a begins → no overlap

One piece of fine print before the fight. Some problems treat intervals as closed (endpoints included, so [1,2] and [2,3] touch and count as overlapping) and some as half-open (the end is excluded, so they don't). In today's problem, touching endpoints do overlap. In Boss 3, they won't. Always read the problem's fine print on endpoints; it flips answers on you silently.

The story

An assistant keeps an executive's agenda in perfect shape: sorted by start, zero overlaps. Today it reads [[1,2],[4,7],[9,11],[14,16]]. Then the executive breezes past and drops a new booking on the desk: [5,10]. "Slot it in."

The assistant doesn't panic and doesn't rewrite the book. She walks the agenda once, left to right:

[1,2]   ends at 2, before the new 5 starts   → keep as is
[4,7]   touches 5..10                        → swallow it, block grows to [4,10]
[9,11]  starts at 9, inside the block        → swallow it, block grows to [4,11]
[14,16] starts past 11                       → block is done, keep the rest as is

agenda: [[1,2],[4,11],[14,16]]

Three phases. Before, overlap, after. The overlapping ones don't get negotiated with, they get absorbed: the block's start is the smallest start seen, its end is the biggest end seen. One pass, agenda repaired.

The problem, dressed up properly

You are given an array of non-overlapping intervals sorted in ascending order by start, and a new interval [start, end]. Insert the new interval so that the result is still sorted and still non-overlapping, merging where necessary. Return the resulting array.

LeetCode 57.

The naive attempt

Toss the new interval in, re-sort, merge everything from scratch:

def insert(intervals, new_interval):
    everything = intervals + [new_interval]
    everything.sort(key=lambda iv: iv[0])        # re-sort ALL of it
    merged = []
    for start, end in everything:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

This works. It's O(n log n), it passes, and it's also a confession: you were handed a sorted, non-overlapping agenda, the single most valuable gift an interval problem can give you, and you shredded it and rebuilt it from the pile. That full sort-and-merge is a real weapon, but it's Boss 2's weapon, for when the input actually is a pile. Here the order already exists. Use it.

The weapon: the three-phase walk

The new interval splits the sorted agenda into three zones, and each zone gets exactly one treatment:

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    start, end = new_interval
    result = []
    i, n = 0, len(intervals)
 
    # phase 1: everything that ends before the new one starts
    while i < n and intervals[i][1] < start:
        result.append(intervals[i])
        i += 1
 
    # phase 2: absorb everything that overlaps the new interval
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])      # block start = smallest start
        end = max(end, intervals[i][1])          # block end = biggest end
        i += 1
    result.append([start, end])                  # the merged block, exactly once
 
    # phase 3: everything after
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

No sort. No re-scan. The overlap test from the top of the dungeon shows up twice, split across the two loop conditions: phase 1 runs while the old interval ends strictly before the new one starts (that's "no overlap, old is left"), phase 2 runs while the old interval starts at or before the new end (that's "overlap"). Phase 3 is whatever survives both.

Watching it work

Agenda [[1,2],[4,7],[9,11],[14,16]], new booking [5,10]:

phase 1: [1,2]    ends 2, before 5        → copy       result [[1,2]]
         [4,7]    ends 7, not before 5    → phase 1 over
phase 2: [4,7]    starts 4, at most 10    → absorb     block [4,10]
         [9,11]   starts 9, at most 10    → absorb     block [4,11]
         [14,16]  starts 14, past 11      → stop, append block
phase 3: [14,16]                          → copy

result [[1,2],[4,11],[14,16]] ✓

Same trace as the assistant's walk, one visit per interval, done.

Gotchas

1. Appending the block in the wrong place. The merged block gets appended exactly once, after phase 2's loop ends. Put the append inside the loop and you emit partial blocks; forget it entirely and a new interval that lands after everything (phase 2 never runs a single absorb) still needs that append. It's not conditional.

2. Endpoint strictness flipped. Phase 1 is strictly "ends before the new one starts". Make it "at most" and a touching booking pair like [1,2] with new [2,5] gets copied as-is instead of merged, and this problem says touching counts. Boss 3 will say the opposite. Fine print, every time.

3. Min-maxing the wrong ends. The block's start is the min of starts, the end is the max of ends. Swap one and the block shrinks while absorbing, quietly deleting meetings from the calendar.

4. Forgetting the empty agenda. intervals = [] means phases 1 and 3 do nothing and the answer is just [new_interval]. The three-loop shape handles it for free, but hand-rolled index juggling often doesn't.

5. Reaching for a sort anyway. It gives the right answer, so it feels safe. But you paid O(n log n) for information you already owned, and in the interview follow-up ("input is sorted, can you do better?") the three-phase walk is the expected answer.

Complexity

One pass, every interval visited exactly once across the three phases, constant work each.

Time: O(n). Space: O(n) for the output (O(1) extra beyond it).

Boss down. XP gained.

The assistant slides the repaired page back across the desk before the executive reaches the elevator. Three meetings became one block, nothing was re-sorted, nothing was read twice.

What you walked away with:

• An interval is [start, end], and one test rules them all: overlap means a.start is at most b.end and b.start is at most a.end, or flipped, no overlap only when one ends before the other begins
• Closed vs half-open endpoints change whether touching intervals overlap; read the fine print per problem
• The three-phase walk: copy the before, absorb the overlap with min-start and max-end, copy the after
• Sorted input is a gift; spending a sort on it is paying for something you already own

Next up: Boss 2 — The Shift Roster. Nobody hands you a tidy agenda in real life: a messy pile of overlapping shifts, and the sort-then-sweep move that runs the whole dungeon.