Insert Interval

Problem Statement

Given a sorted list of non-overlapping intervals, insert a new interval into the list. Merge if necessary, and return the result still sorted and non-overlapping.

Input

• intervals — a sorted list of pairwise non-overlapping intervals.
• newInterval — a single interval [start, end] to insert.

intervals   = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]

Output

The resulting list of intervals, still sorted by start and still non-overlapping after the new interval is merged in.

[[1,2],[3,10],[12,16]]

Constraints

• 0 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2 and newInterval.length == 2
• 0 ≤ startᵢ ≤ endᵢ ≤ 10⁵
• intervals is sorted by startᵢ in ascending order.

Intuition

Three-phase sweep — the input is already sorted, so a single pass is enough:

1. Before — collect all intervals that end before newInterval starts. No overlap, keep as-is.
2. Merge — for every interval that overlaps newInterval, expand newInterval to cover it.
3. After — append all remaining intervals untouched.

No sorting needed since the input is pre-sorted.

intervals:  [1,2]   [3,5]   [6,7]   [8,10]   [12,16]
new:                  [==== 4 ======== 8 ====]
 
Phase 1 (Before):  [1,2] ends at 2 < 4   →  keep [1,2]
Phase 2 (Merge):
  [3,5]  → 3 ≤ 8  → merge → new = [3, 8]
  [6,7]  → 6 ≤ 8  → merge → new = [3, 8]
  [8,10] → 8 ≤ 8  → merge → new = [3, 10]
  → add [3, 10]
Phase 3 (After):   [12,16] → keep [12,16]
 
Result:  [[1,2], [3,10], [12,16]]

Solution

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    result = []
    i, n = 0, len(intervals)
 
    # Phase 1: intervals entirely before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
 
    # Phase 2: merge overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)
 
    # Phase 3: remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
 
    return result

function insert(intervals: number[][], newInterval: number[]): number[][] {
    const result: number[][] = [];
    let i = 0;
    const n = intervals.length;
 
    // Phase 1: before
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }
 
    // Phase 2: merge
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push(newInterval);
 
    // Phase 3: after
    while (i < n) {
        result.push(intervals[i]);
        i++;
    }
 
    return result;
}

Complexity

Edge Case Thinking