Insert Interval (LeetCode 57) Solution

The problem

You get a list of non-overlapping intervals sorted by start, and one new interval. Insert the new interval so the list stays sorted and non-overlapping, merging wherever it overlaps existing intervals. Return the new list.

Input:  intervals = [[1, 3], [6, 9]], new = [2, 5]
Output: [[1, 5], [6, 9]]

[2, 5] overlaps [1, 3], so they merge into [1, 5]. [6, 9] starts after 5 and is untouched.

How to think about it

Start with brute force. Append the new interval and run the full Merge Intervals algorithm: sort, then sweep. That is O(n log n), and it throws away the fact that the input is already sorted.

The key insight: the list splits into three runs. Because the existing intervals are sorted and disjoint, they fall into three consecutive groups relative to new:

Intervals that end before new starts (end < new[0]). They come first, unchanged.
Intervals that overlap new (start <= new[1]). Absorb each one into new by taking the min start and max end.
Everything left, which starts after new ends. Copy unchanged.

One pointer, three loops. A single index i moves forward through all three phases, so the whole thing is one linear pass. No sorting needed.

Which pattern is this? Merge intervals on already sorted input. The tell is “sorted, non-overlapping list” plus “insert one interval”.

Approach

While intervals[i] ends before new starts, append it to res and advance i.
While intervals[i] starts at or before new ends, widen new to cover it and advance i.
Append the (possibly widened) new.
Append every remaining interval.
Return res.

Solution

def insert(intervals, new):
    res = []; i = 0; n = len(intervals)
    while i < n and intervals[i][1] < new[0]:          # phase 1: entirely before new
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:         # phase 2: overlaps new, absorb it
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]; i += 1
    res.append(new)
    while i < n:                                       # phase 3: entirely after new
        res.append(intervals[i]); i += 1
    return res
# insert([[1,3],[6,9]], [2,5]) -> [[1,5],[6,9]]

Dry run

The main example is short, so here is a second one that exercises every phase: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4, 8].

Phase	Interval seen	`new` after	`res` after
1 (before)	[1, 2]	[4, 8]	[[1, 2]]
2 (merge)	[3, 5]	[3, 8]	[[1, 2]]
2 (merge)	[6, 7]	[3, 8]	[[1, 2]]
2 (merge)	[8, 10]	[3, 10]	[[1, 2]]
append `new`	—	[3, 10]	[[1, 2], [3, 10]]
3 (after)	[12, 16]	[3, 10]	[[1, 2], [3, 10], [12, 16]]

For the main example, phase 1 copies nothing (3 is not < 2), phase 2 merges [1, 3] into [1, 5], and phase 3 copies [6, 9].

Complexity

Time: O(n). Each interval is visited once across the three loops.
Space: O(n). The output list.

Edge cases and pitfalls

Empty list returns [new].
New interval at the very end ([[1, 2]], [5, 6]): phase 1 copies everything, then new is appended last.
New interval at the very start ([[3, 4]], [0, 1]): phases 1 and 2 do nothing, new goes first.
Boundary conditions: touching intervals merge. [[1, 3]] with [3, 5] gives [[1, 5]] because phase 1 uses < and phase 2 uses <=.
Re-sorting works but is O(n log n) and signals you missed that the input is sorted.

Merge Intervals (LeetCode 56): the general version when the input is unsorted.
Non-overlapping Intervals (LeetCode 435): remove intervals instead of merging them.
My Calendar I (LeetCode 729): inserting intervals one at a time, rejecting overlaps instead of merging.