Problem 39 · Intervals

Insert Interval

MediumClassic DSA & systems

01Problem

Given sorted non-overlapping intervals and a new interval, insert it and merge as needed, returning sorted non-overlapping intervals.

02Key insight

Three linear phases: copy intervals ending before the new one, absorb all that overlap by widening the new interval, then copy the rest. No re-sort needed.

03Solution

solution.pypython11 lines

def insert_interval(intervals: list[list[int]], new: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    start, end = new
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < start:
        result.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= end:
        start, end = min(start, intervals[i][0]), max(end, intervals[i][1]); i += 1
    result.append([start, end])
    result.extend(intervals[i:])
    return result

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert insert_interval([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
assert insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [[1, 2], [3, 10], [12, 16]]
assert insert_interval([], [5, 7]) == [[5, 7]]
assert insert_interval([[1, 5]], [6, 8]) == [[1, 5], [6, 8]]

04Staff-level follow-up

Millions of intervals and frequent inserts? Binary-search (bisect) the overlap range for O(log n) location, though splicing a Python list is still O(n); use an interval tree or SortedList for true O(log n).