[57] 插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]

输出：[[1,5],[6,9]]

示例 2：

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

输出：[[1,2],[3,10],[12,16]]

解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示：

0 <= intervals.length <= 10^4

intervals[i].length == 2

0 <= starti <= endi <= 10^5

intervals 根据 starti 按 升序 排列

newInterval.length == 2

0 <= start <= end <= 10^5

解法

这道题的解法有点类似于合并区间，但是要复杂一些。首先我们要找到插入点，然后根据插入点的位置进行不同的操作。

难点在于，需要想清楚到底有几种互斥的情况，以及如何处理。

我将插入点分为四种情况：

1. 插入点在最右侧，或者原数组为空，此时直接插入即可。
2. 插入点在最左侧，此时直接插入到头部即可。
3. 插入点在中间，此时需要找到插入点的位置，这里又会细分成两种情况。
   • 插入的集合与原数组没有交集，直接从插入点插入即可。
   • 插入的集合与原数组有交集，此时需要合并交集处的集合。并确立好新集合的左右边界，然后替换掉原数组中的集合。

理清了这几点后，代码就比较好写了。

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const start = newInterval[0];
  const end = newInterval[1];

  if (intervals.length === 0 || intervals[intervals.length - 1][1] < start) {
    // 插入点在最右侧
    intervals.push(newInterval);
  } else if (intervals[0][0] > end) {
    // 插入点在最左侧
    intervals.unshift(newInterval);
  } else {
    // 找到插入位置
    let left = 0;
    let right = intervals.length - 1;
    while (intervals[left][1] < start) {
      left++;
    }
    while (intervals[right][0] > end) {
      right--;
    }

    if (left > right) {
      // 说明此时 newInterval 与原数组没有交集，直接插入
      intervals.splice(left, 0, newInterval);
    } else {
      // 有交集，替换交集处之间的集合
      const newItem = [Math.min(intervals[left][0], newInterval[0]), Math.max(intervals[right][1], newInterval[1])];
      intervals.splice(left, right - left + 1, newItem);
    }
  }
  return intervals;
}