Insert Interval Without Re-Sorting Anything

This one is a Medium-rated classic reported from Google, LinkedIn, Amazon interviews: "Insert Interval". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Merge Intervals pattern on sight. Part 2 of 11 in the Merge Intervals arc.

The Problem

Given non-overlapping intervals sorted by start and a new interval, insert it and merge as needed, returning a sorted, non-overlapping result. Appending and calling your Merge Intervals routine works — and wastes the sortedness the problem hand-delivers, which interviewers read as pattern-matching without thinking.

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

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Sorted, disjoint input means the new interval interacts with one contiguous run of intervals only. Everything strictly before, one absorbed middle, everything strictly after — a three-phase linear scan with no sort.

The Approach

Phase one: copy intervals whose end is below the new start. Phase two: while intervals overlap the new one (their start at most the new end), fold them in by taking min of starts and max of ends. Phase three: copy the rest. Append the folded interval between phases two and three.

State the overlap condition once, precisely — iv[0] <= new_end and iv[1] >= new_start — and the three phases fall out of its negations. Sloppy overlap predicates are where this question kills candidates.

Python Solution

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    """Insert new_interval into sorted disjoint intervals, merging overlaps."""
    ns, ne = new_interval
    result: list[list[int]] = []
    i, n = 0, len(intervals)

    while i < n and intervals[i][1] < ns:      # strictly before
        result.append(intervals[i])
        i += 1

    while i < n and intervals[i][0] <= ne:     # overlapping: absorb
        ns = min(ns, intervals[i][0])
        ne = max(ne, intervals[i][1])
        i += 1
    result.append([ns, ne])

    result.extend(intervals[i:])               # strictly after
    return result

Complexity

• Time: O(n) — single scan, no sorting
• Space: O(n) — the rebuilt output list

Interview Tips and Follow-Ups

• Say explicitly why you are not sorting: the input's invariant makes O(n) possible, and using given invariants is the senior move.
• Empty input and fully-contained new intervals ([1, 5] absorbing [2, 3]) are the edge cases to volunteer unprompted.
• In-place insertion into a Python list is O(n) per shift anyway — building a new list is not lazy, it is optimal. Preempt the objection.

If this clicked, continue the Merge Intervals arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.