Insert Interval: Add a Range to a Sorted List and Merge Overlaps

Problem

You have 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 needed, and return the result. Intervals that share an endpoint count as overlapping. This is widely known as LeetCode 57, Insert Interval.

Examples

intervals = [[1, 2], [4, 6], [9, 11]],  new = [5, 9]    ->  [[1, 2], [4, 11]]
intervals = [[3, 4]],                   new = [0, 1]    ->  [[0, 1], [3, 4]]
intervals = [],                         new = [2, 3]    ->  [[2, 3]]

Approach 1: brute force

Append the new interval and run the general merge: sort by start and sweep.

def insert_brute(intervals, new):
    merged = []
    for start, end in sorted(intervals + [new]):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Complexity: O(n log n) time because of the sort, O(n) space. Correct, but it ignores that the input is already sorted.

Approach 2: optimal

Key insight: the existing intervals split into three contiguous groups: those entirely before the new interval, those overlapping it, and those entirely after it. Handle each group with its own loop.

Walkthrough on [[1, 2], [4, 6], [9, 11]], new = [5, 9]:

1. Before: [1, 2] ends at 2, before 5 starts: copy it. [4, 6] ends at 6, which is not before 5, so stop.
2. Overlap: [4, 6] starts at 4 ≤ 9, widen new to [4, 9]. [9, 11] starts at 9 ≤ 9, widen to [4, 11]. End of list.
3. Append [4, 11]. Nothing left to copy. Result [[1, 2], [4, 11]].

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

Complexity: O(n) time, O(n) space for the output. Binary search can locate the first overlap in O(log n), but building the output is still O(n).

Tests

import random

for f in (insert, insert_brute):
    assert f([[1, 2], [4, 6], [9, 11]], [5, 9]) == [[1, 2], [4, 11]]
    assert f([[3, 4]], [0, 1]) == [[0, 1], [3, 4]]                 # goes first
    assert f([[3, 4]], [7, 8]) == [[3, 4], [7, 8]]                 # goes last
    assert f([], [2, 3]) == [[2, 3]]                               # empty list
    assert f([[1, 3], [6, 8]], [4, 5]) == [[1, 3], [4, 5], [6, 8]] # gap, no merge
    assert f([[1, 3], [5, 7]], [3, 5]) == [[1, 7]]                 # touches both
    assert f([[2, 3], [5, 6]], [0, 10]) == [[0, 10]]               # swallows all
    assert f([[1, 10]], [4, 5]) == [[1, 10]]                       # contained
    assert f([[-9, -6]], [-7, -1]) == [[-9, -1]]                   # negatives
    assert f([[0, 1]], [10**9, 10**9]) == [[0, 1], [10**9, 10**9]] # large values

random.seed(12)
for _ in range(300):
    base, cur = [], random.randint(-5, 0)
    for _ in range(random.randint(0, 5)):
        s = cur + random.randint(1, 3)
        e = s + random.randint(0, 3)
        base.append([s, e])
        cur = e
    a = random.randint(-8, 20)
    new = [a, a + random.randint(0, 6)]
    assert insert(base, new) == insert_brute(base, new)

Edge cases and pitfalls

• The new interval may go before everything, after everything, or swallow everything; the three-phase loop handles all three without special cases.
• Use strict < in the first loop and <= in the second, so intervals that touch the new one are merged.
• Copy intervals instead of appending references to the input, or later edits to the result will change the caller’s data.

Where this shows up in data engineering

Applying one new booking, outage or late-arriving validity period to an existing timeline is this operation. In an SCD Type 2 table, inserting a corrected history row means finding the rows it overlaps, closing or splitting them, and leaving the rest untouched, which is the same before, overlap and after split.