57.insert-interval.md

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

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

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

---

思路

1. 二分查找插入位置
2. 插入区间
3. 合并

var insert = function (intervals, newInterval) {
  let l = 0,
    r = intervals.length;

  while (l < r) {
    let mid = (l + r) >> 1;
    if (intervals[mid][0] >= newInterval[0]) r = mid;
    else l = mid + 1;
  }
  // 插入位置是l
  intervals.splice(l, 0, newInterval);
  return merge(intervals);
};

var merge = function (intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  let result = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    let last = result[result.length - 1];
    if (last[1] >= intervals[i][0]) {
      last[1] = Math.max(intervals[i][1], last[1]);
    } else {
      result.push(intervals[i]);
    }
  }
  return result;
};