Overview

You are given a sorted array of non-overlapping intervals intervals where intervals[i] = [start, end], and a new interval newInterval = [start, end]. Insert newInterval into intervals such that the list remains sorted and non-overlapping (merge overlapping intervals if necessary).

Implement insertInterval(intervals, newInterval).

Constraints

• intervals is sorted by start in ascending order and already non-overlapping.
• You must return a new sorted, non-overlapping array of intervals.
• Aim for $O(n)$ time — no need to re-sort since input is already sorted.

Examples

insertInterval([[1,3],[6,9]], [2,5]);
// → [[1,5],[6,9]]

insertInterval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]);
// → [[1,2],[3,10],[12,16]]

insertInterval([], [5,7]);
// → [[5,7]]

insertInterval([[1,5]], [2,3]);
// → [[1,5]]  — newInterval fully contained

Notes

• Three-phase approach: (1) add all intervals that end before the new one starts, (2) merge all overlapping intervals with the new one, (3) add all remaining intervals.
• During the merge phase, update newInterval start/end with min/max of overlapping bounds.

Solution

function insertInterval(intervals, newInterval) {
  const result = [];
  let i = 0;
  const n = intervals.length;

  // Phase 1: intervals that come entirely before newInterval
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Phase 2: merge overlapping intervals
  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: intervals that come entirely after
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

Resources

• Insert Interval — LeetCode
• Interval Scheduling — Wikipedia