Insert Interval

35 min · insert()

Your meeting calendar is already clean and ordered. One new booking arrives; rebuilding the whole calendar from scratch would waste the structure you already have.

Given sorted, pairwise disjoint intervals and one newInterval, insert the new range, merge every overlap it creates, and return the resulting intervals in ascending start order.

Pairwise disjoint means no two existing intervals share any point. Endpoints count: if the new range ends where an existing range begins, those ranges merge.

A few ground rules:

Every interval has the form [start, end] with start <= end.
The existing intervals are sorted by start and have a strict gap between neighbors.
The input may contain no existing intervals at all.

Constraints

0 <= intervals.length <= 100_000
Every interval and newInterval contains exactly two integers: [start, end].
intervals is sorted by ascending start and pairwise disjoint.
0 <= start <= end <= 1_000_000_000
0 <= newInterval[0] <= newInterval[1] <= 1_000_000_000

Hints

There are three regions

Existing intervals fall before the new range, overlap it, or fall after it. The sorted order lets you process those regions from left to right.

Copy the finished prefix

While an interval ends strictly before the new range starts, add it unchanged. The strict comparison matters because touching endpoints must merge.

Grow one combined range

While the next start is no greater than the combined end, update both boundaries. Add that combined range once, then copy the untouched suffix.

Follow-up

Can you prove that each existing interval is inspected at most once, even when the new range swallows the entire input?

Visible cases

Examples

Example 1

ready

Input: intervals = [ [ 1, 3 ], [ 6, 9 ] ] newInterval = [ 2, 5 ]
Expected: [ [ 1, 5 ], [ 6, 9 ] ]
Why: the new range overlaps the first interval but stops before the second

Example 2

ready

Input: intervals = [ [ 1, 2 ], [ 3, 5 ], [ 6, 7 ], [ 8, 10 ], [ 12, 16 ] ] newInterval = [ 4, 8 ]
Expected: [ [ 1, 2 ], [ 3, 10 ], [ 12, 16 ] ]
Why: one insertion bridges three existing ranges into [3, 10]

Example 3

ready

Input: intervals = [] newInterval = [ 5, 7 ]
Expected: [ [ 5, 7 ] ]
Why: with no existing ranges, the new interval becomes the whole result

Interview signal

Asked at

AmazonGoogleLinkedIn

Append + merge

You already know a general tool: append the new interval, sort everything by start, and run the Merge Intervals sweep. It works, but the sort repeats information the input already guarantees.

def insert(
    intervals: list[list[int]],
    new_interval: list[int],
) -> list[list[int]]:
    ordered = [interval[:] for interval in intervals]
    ordered.append(new_interval[:])
    ordered.sort(key=lambda interval: interval[0])
 
    merged: list[list[int]] = []
    for start, end in ordered:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

Time O(n log n) for sorting. Space O(n) for the copied intervals and result.

Three-phase sweep

The existing ranges are already sorted and disjoint, so one pass can split them into three phases:

Copy every interval strictly before the new range.
Fold every touching or overlapping interval into the new range.
Copy every interval strictly after the combined range.

def insert(
    intervals: list[list[int]],
    new_interval: list[int],
) -> list[list[int]]:
    result: list[list[int]] = []
    i = 0
    start, end = new_interval
 
    while i < len(intervals) and intervals[i][1] < start:
        result.append(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
    result.append([start, end])
 
    while i < len(intervals):
        result.append(intervals[i][:])
        i += 1
 
    return result

The first phase uses end < start, while the merging phase uses start <= end. Those two comparisons make touching endpoints join the combined interval.

Time O(n) because the index only moves forward. Space O(n) for the returned array; the sweep itself uses O(1) extra state.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayintervals: int[][] · newInterval: int[]

Expected

Run: visible + custom · Submit: full suite