每天一道leetcode(Day 54)

57. 插入区间

题目描述

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例

• 示例  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] 重叠。

解题思路

思路：见缝插针

具体步骤：

• 在有序区间列表里插入一个区间，取得新区间的左边界 newStart，右边界 newEnd
  遍历原区间
  • 当 newStart 大于 当前区间的右边界时，说明两个区间没有交集，不用合并，又因为原区间列表有序，因此可以直接将当前区间排入新的区间列表中
  • 当 newEnd 大于 当前区间的左边界时说明两个区间有重合，所以将两个区间的最小左边界和最大右边界重新组合为新的区间，即合并区间，然后将其排入新区间列表中
• 当区间列表没有遍历完时将剩下的区间列表添加到列表后面即可

代码

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  let res = [],
    len = intervals.length,
    i = 0,
    newStart = newInterval[0],
    newEnd = newInterval[1];
  // 区间没有重合
  while (i < len && newStart > intervals[i][1]) {
    res.push(intervals[i]);
    i++;
  }
  // 区键有重合
  while (i < len && newEnd >= intervals[i][0]) {
    newStart = Math.min(newStart, intervals[i][0]);
    newEnd = Math.max(newEnd, intervals[i][1]);
    i++;
  }
  res.push([newStart, newEnd]);
  // 添加剩余区键
  while (i < len) {
    res.push(intervals[i]);
    i++;
  }
  return res;
};

参考

57. 插入区间