insert-interval.ts

/**
 * 57. Insert Interval  (Medium)
 * Link: https://leetcode.com/problems/insert-interval/
 *
 * Given a list of non-overlapping intervals sorted by start and a `newInterval`,
 * insert it and merge as needed so the result stays sorted and non-overlapping.
 *
 * Example:
 *   Input:  intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
 *   Output: [[1, 5], [6, 9]]
 *
 * Approach:
 *   Single linear pass over the already-sorted intervals, in three phases:
 *   (1) copy intervals ending before newInterval starts; (2) merge every
 *   interval that overlaps newInterval by widening its bounds; (3) copy the rest.
 *   No sorting needed since input is pre-sorted.
 *
 * Time:  O(n)
 * Space: O(n)  — the output list.
 */
export function insertInterval(
  intervals: number[][],
  newInterval: number[],
): number[][] {
  const result: number[][] = [];
  let [start, end] = newInterval;
  let i = 0;
  const n = intervals.length;

  // 1) intervals strictly before the new one
  while (i < n && intervals[i][1] < start) {
    result.push(intervals[i]);
    i++;
  }

  // 2) merge all overlapping intervals into [start, end]
  while (i < n && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);

  // 3) intervals strictly after the new one
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}