Insert Interval（插入区间）

题目 / Problem

中文： 给定一个互不重叠的区间数组 intervals，其中 intervals[i] = [startᵢ, endᵢ] 表示第 i 个区间的起点和终点。所有区间已经按照 startᵢ 升序排列。

另给一个新区间 newInterval = [start, end]。请将它插入 intervals，使结果仍按起点升序排列，并且所有区间仍互不重叠。如果存在重叠区间，需要将它们合并。

如果两个区间至少共享一个点，就认为它们重叠。例如 [1,3] 和 [3,5] 在位置 3 相交，因此需要合并为 [1,5]。

返回插入后的区间数组。无需原地修改 intervals，可以创建并返回一个新数组。

English: You are given an array of non-overlapping intervals intervals, where intervals[i] = [startᵢ, endᵢ] represents the start and end of the ith interval. The intervals are sorted in ascending order by startᵢ.

You are also given an interval newInterval = [start, end]. Insert it into intervals so that the result remains sorted by start and contains no overlapping intervals. Merge overlapping intervals when necessary.

Two intervals are considered overlapping if they share at least one point. Return the intervals after insertion. You do not need to modify intervals in place.

示例 / Examples

Example 1

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

区间 [1,3] 与新区间 [2,5] 重叠，合并后得到 [1,5]；区间 [6,9] 位于其右侧。
Interval [1,3] overlaps with [2,5], producing [1,5]; interval [6,9] remains to its right.

Example 2

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

新区间 [4,8] 与 [3,5]、[6,7] 和 [8,10] 重叠。连续合并后得到 [3,10]。
The new interval [4,8] overlaps with [3,5], [6,7], and [8,10]. Merging them produces [3,10].

注意 [4,8] 与 [8,10] 共享端点 8，因此也属于重叠。
Notice that [4,8] and [8,10] share endpoint 8, so they overlap as well.

约束 / Constraints

• 0 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= startᵢ <= endᵢ <= 10⁵
• intervals 按 startᵢ 升序排列。
  intervals is sorted in ascending order by startᵢ.
• newInterval.length == 2
• 0 <= start <= end <= 10⁵

解题思路：分成三个阶段 / Approach: Three Phases

原区间已经有序且互不重叠，因此不需要重新排序。只需从左向右处理三个部分：
The original intervals are already sorted and non-overlapping, so no re-sorting is needed. Process them from left to right in three phases:

第一阶段：新区间左侧的区间 / Phase 1: Intervals Before the New Interval

如果当前区间的终点严格小于新区间的起点：
If the current interval ends strictly before the new interval starts:

currentEnd < newStart

它们完全不重叠，可以直接加入结果。
They are completely disjoint, so append the current interval directly.

第二阶段：合并所有重叠区间 / Phase 2: Merge All Overlapping Intervals

只要当前区间的起点小于或等于正在合并区间的终点，就存在重叠：
As long as the current interval starts at or before the merged interval ends, they overlap:

currentStart <= mergedEnd

更新合并区间的边界：
Update the merged boundaries:

mergedStart = min(mergedStart, currentStart)
mergedEnd   = max(mergedEnd, currentEnd)

所有重叠区间处理完后，将合并后的新区间加入结果。
After processing every overlap, append the merged new interval.

第三阶段：新区间右侧的区间 / Phase 3: Intervals After the New Interval

剩余区间都位于合并区间右侧，并且互不重叠，可以直接依次加入结果。
Every remaining interval lies to the right of the merged interval and can be appended directly.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
function insert(intervals, newInterval) {
  const result = [];
  let index = 0;
  let [mergedStart, mergedEnd] = newInterval;

  // 1. 添加完全位于新区间左侧的区间。
  // 1. Append intervals completely before the new interval.
  while (
    index < intervals.length &&
    intervals[index][1] < mergedStart
  ) {
    result.push(intervals[index]);
    index++;
  }

  // 2. 合并所有与新区间重叠的区间。
  // 2. Merge every interval overlapping the new interval.
  while (
    index < intervals.length &&
    intervals[index][0] <= mergedEnd
  ) {
    mergedStart = Math.min(mergedStart, intervals[index][0]);
    mergedEnd = Math.max(mergedEnd, intervals[index][1]);
    index++;
  }

  result.push([mergedStart, mergedEnd]);

  // 3. 添加完全位于新区间右侧的剩余区间。
  // 3. Append all remaining intervals after the new interval.
  while (index < intervals.length) {
    result.push(intervals[index]);
    index++;
  }

  return result;
}

这里使用局部变量 mergedStart 和 mergedEnd，不会修改传入的 newInterval。
Local variables mergedStart and mergedEnd are used, so the input newInterval is not modified.

执行过程 / Walkthrough

以 Example 2 为例：
For Example 2:

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

加入合并后的 [3,10]，再追加 [12,16]，最终得到：
Append [3,10], followed by [12,16], producing:

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

边界情况 / Edge Cases

空数组 / Empty Input

intervals = [], newInterval = [2,5]
result    = [[2,5]]

插入到最前面 / Insert at the Beginning

intervals = [[3,5],[7,9]], newInterval = [1,2]
result    = [[1,2],[3,5],[7,9]]

插入到最后面 / Insert at the End

intervals = [[1,2],[3,5]], newInterval = [6,8]
result    = [[1,2],[3,5],[6,8]]

覆盖所有区间 / Cover Every Interval

intervals = [[2,3],[5,7]], newInterval = [1,10]
result    = [[1,10]]

只共享端点 / Share Only an Endpoint

intervals = [[1,3]], newInterval = [3,5]
result    = [[1,5]]

共享端点仍属于重叠，所以不能保留为两个独立区间。
Sharing an endpoint still counts as overlap, so the intervals cannot remain separate.

复杂度 / Complexity

设原数组包含 n 个区间。
Let the original array contain n intervals.

• 时间复杂度：O(n)，每个区间最多处理一次。
  Time: O(n), because each interval is processed at most once.
• 空间复杂度：O(n)，返回结果最多包含 n + 1 个区间。
  Space: O(n), because the returned array may contain up to n + 1 intervals.
• 如果不计算必须返回的结果数组，额外辅助空间为 O(1)。
  Excluding the required output array, the auxiliary space is O(1).

为什么不需要排序？ / Why Is Sorting Unnecessary?

题目保证 intervals 已按起点升序排列，并且内部没有重叠。新区间只会影响一段连续的区间：左侧区间保持不变，中间区间合并，右侧区间保持不变。
The input is already sorted and non-overlapping. The new interval affects only one contiguous portion: left intervals remain unchanged, middle intervals merge, and right intervals remain unchanged.

因此一次线性扫描就能保持最终结果有序。若重新排序，时间复杂度会不必要地增加到 O(n log n)。
One linear scan therefore preserves the final ordering. Sorting again would unnecessarily increase the time complexity to O(n log n).

易错点 / Common Pitfalls

• 两个区间共享端点时也算重叠，例如 [1,3] 和 [3,5]。
  Intervals sharing an endpoint overlap, such as [1,3] and [3,5].
• 左侧无重叠条件是 currentEnd < mergedStart，不能写成 <=。
  The non-overlapping-left condition is currentEnd < mergedStart, not <=.
• 重叠条件是 currentStart <= mergedEnd，必须包含等号。
  The overlap condition is currentStart <= mergedEnd, including equality.
• 合并完成后不要忘记将新区间加入结果。
  Append the merged new interval after the overlap loop.
• intervals 可能为空，新区间可能位于最前面、最后面或覆盖所有区间。
  intervals may be empty, and the new interval may come first, last, or cover every existing interval.
• 不需要重新排序，也不需要原地修改输入数组。
  There is no need to sort again or modify the input array in place.