Insert New Interval and Merge Overlapping Intervals

The Insert Interval problem (LeetCode 57) is a foundational algorithmic challenge that models real-world calendar scheduling, database range locks, and timeline coalescing. Given an array of non-overlapping intervals sorted in ascending order by their start times, we must insert a new interval and merge any overlapping intervals so that the resulting sequence remains mutually exclusive and sorted in ascending order.

Problem Statement and Examples

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represents the start and end of the i-th event, sorted in ascending order by start_i. You are also given a new interval newInterval = [newStart, newEnd].

Insert newInterval into intervals such that intervals remains sorted in ascending order by start time and contains no overlapping intervals (merging overlapping ranges if necessary).

Example 1: Bridging Two Existing Intervals

Input:  intervals = [[1, 3], [4, 5], [6, 7], [8, 10]], newInterval = [5, 6]
Output: [[1, 3], [4, 7], [8, 10]]
Explanation: The new interval [5, 6] touches and overlaps with both [4, 5] and [6, 7], coalescing them into [4, 7].

Example 2: Spanning Multiple Intervals

Input:  intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 9]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: The new interval [4, 9] overlaps with [3, 5], [6, 7], and [8, 10], merging all three into [3, 10].

Constraints

0 <= intervals.length <= 10^5
intervals[i].length == 2
0 <= start_i <= end_i <= 10^9
intervals is sorted in ascending order by start_i.

Three-Phase Linear Sweep Architecture

Because the input array is already sorted and non-overlapping, appending newInterval and re-sorting the entire collection in O(n log n) time wastes the existing ordering invariant. Instead, a single-pass linear sweep solves the interval merging problem in optimal O(n) time by partitioning the array into three disjoint phases around newInterval = [newStart, newEnd]:

Phase 1 — Strictly Preceding Intervals (end_i < newStart): Every interval whose end time is strictly less than newInterval[0] cannot overlap with the new interval. Append these directly to the output list.
Phase 2 — Overlapping Intervals (start_i <= newEnd): Once Phase 1 finishes, any subsequent interval whose start time is less than or equal to the current newInterval[1] overlaps with newInterval. Expand newInterval in place to absorb each overlapping range:
```
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
```
Once the loop exits, push the fully coalesced newInterval into the output list.
Phase 3 — Strictly Succeeding Intervals (start_i > newEnd): All remaining intervals start strictly after the merged interval ends. Append them directly to the output list.

C++20 Implementation

The C++ implementation pre-allocates vector capacity to prevent intermediate heap reallocations during the three-phase traversal:

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<std::vector<int>> insertInterval(
    const std::vector<std::vector<int>>& intervals,
    std::vector<int> newInterval
) {
    std::vector<std::vector<int>> result;
    result.reserve(intervals.size() + 1);

    std::size_t i = 0;
    const std::size_t n = intervals.size();

    // Phase 1: Append all intervals that end strictly before newInterval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        ++i;
    }

    // Phase 2: Coalesce all overlapping intervals into newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = std::min(newInterval[0], intervals[i][0]);
        newInterval[1] = std::max(newInterval[1], intervals[i][1]);
        ++i;
    }
    result.push_back(newInterval);

    // Phase 3: Append all remaining intervals that start after newInterval ends
    while (i < n) {
        result.push_back(intervals[i]);
        ++i;
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> intervals = {{1, 3}, {6, 9}};
    std::vector<int> newInterval = {2, 5};

    auto merged = insertInterval(intervals, newInterval);
    for (const auto& interval : merged) {
        std::cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    std::cout << "\n"; // Outputs: [1, 5] [6, 9]
    return 0;
}

TypeScript Implementation for Scheduling Engines

In full-stack Node.js and React booking applications, intervals are commonly represented as tuple pairs [number, number]. Below is a non-mutating TypeScript implementation that preserves input immutability:

export type Interval = [number, number];

export function insertAndMergeInterval(
  intervals: ReadonlyArray<Interval>,
  newInterval: Interval
): Interval[] {
  const result: Interval[] = [];
  let [mergedStart, mergedEnd] = newInterval;
  let i = 0;
  const n = intervals.length;

  // Phase 1: Intervals strictly before the new interval
  while (i < n && intervals[i][1] < mergedStart) {
    result.push([intervals[i][0], intervals[i][1]]);
    i++;
  }

  // Phase 2: Overlapping intervals that touch or intersect [mergedStart, mergedEnd]
  while (i < n && intervals[i][0] <= mergedEnd) {
    mergedStart = Math.min(mergedStart, intervals[i][0]);
    mergedEnd = Math.max(mergedEnd, intervals[i][1]);
    i++;
  }
  result.push([mergedStart, mergedEnd]);

  // Phase 3: Intervals strictly after the merged interval
  while (i < n) {
    result.push([intervals[i][0], intervals[i][1]]);
    i++;
  }

  return result;
}

Time and Space Complexity Analysis

Time Complexity — O(n): The index pointer i advances monotonically from 0 to n - 1 across the three while loops, visiting each interval exactly once and performing O(1) comparisons per step.
Auxiliary Space Complexity — O(1) (excluding output): Aside from the output array of size at most n + 1, the algorithm uses a constant number of scalar variables.

Boundary Conditions and Edge Cases

Empty Input Array: When intervals = [] and newInterval = [5, 7], Phases 1, 2, and 3 skip their loop bodies and return [[5, 7]].
Disjoint Insertion at Head or Tail: If newInterval precedes all existing intervals (e.g., [0, 1] before [[3, 4], [5, 6]]) or follows all intervals, Phase 2 executes zero iterations and inserts newInterval cleanly in sorted order.
Complete Containment: If an existing interval completely encompasses newInterval (e.g., [[1, 10]] with newInterval = [3, 6]), Phase 2 absorbs it and outputs [[1, 10]].