026. Insert One Interval

Why this mechanism works

The sorted input has three phases relative to the new interval: entirely before, overlapping, and entirely after. Only the middle phase can enlarge the interval being inserted. Its growing end can cause more intervals to enter the overlap phase, so compare against the updated end each time.

State and boundaries

i is the next unread interval. start,end describe the accumulated insertion interval. output holds finalized intervals before it.

Protocol

1. Copy intervals ending before the new start.
2. Merge every next interval starting no later than the growing end.
3. Append the accumulated insertion interval.
4. Copy the remaining suffix.

Visualization

before | overlapping block | after
       [ new, growing end ]
commit only after overlap block ends

Python implementation

def insert_interval(intervals, new):
    start, end = new
    output = []
    i = 0
    while i < len(intervals) and intervals[i][1] < start:
        output.append(list(intervals[i]))
        i += 1
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    output.append([start, end])
    output.extend(list(pair) for pair in intervals[i:])
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 insert_interval: start, end = new
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=2; end=5

L3 insert_interval: output = []
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=2; end=5; output=[]

L4 insert_interval: i = 0
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=2; end=5; output=[]; i=0

L9 insert_interval: start = min(start, intervals[i][0])
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=1; end=5; output=[]; i=0

L11 insert_interval: i += 1
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=1; end=5; output=[]; i=1

L12 insert_interval: output.append([start, end])
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=1; end=5; output=[[1, 5]]; i=1

L13 <genexpr>: output.extend(list(pair) for pair in intervals[i:])
.0=list_iterator; pair=[6, 9]

L13 <genexpr>: output.extend(list(pair) for pair in intervals[i:])
.0=list_iterator; pair=[6, 9]

L13 insert_interval: output.extend(list(pair) for pair in intervals[i:])
intervals=[[1, 3], [6, 9]]; new=[2, 5]; start=1; end=5; output=[[1, 5], [6, 9]]; i=1

L2 insert_interval: start, end = new
intervals=[]; new=[2, 4]; start=2; end=4

L3 insert_interval: output = []
intervals=[]; new=[2, 4]; start=2; end=4; output=[]

L4 insert_interval: i = 0
intervals=[]; new=[2, 4]; start=2; end=4; output=[]; i=0

L12 insert_interval: output.append([start, end])
intervals=[]; new=[2, 4]; start=2; end=4; output=[[2, 4]]; i=0

L13 <genexpr>: output.extend(list(pair) for pair in intervals[i:])
.0=list_iterator

Why the solution is correct

Intervals in the first phase cannot overlap the insertion. The middle phase preserves their union by extending endpoints and continues until a genuine gap appears. Sorted order ensures every remaining interval lies after that gap, so appending it is safe.

Time and space

O(n) time and O(n) output space; the input's existing order avoids another sort.

Common mistakes

Testing overlap only against the original new end can miss a chain of overlaps. Appending the new interval too early commits incomplete state.

Reasoning card

Transfer exercise

Explain why arbitrary unsorted inputs require sorting or a different data structure before this three-phase scan.