【一天一大 lee】插入区间 (难度:困难) - Day20201104

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

输入：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] 重叠。

  intervals: ...[1,3],[6,9]...
  newInterval: [4,5]
  3<4  && 5<6

  intervals: ...[1,3], ... ,[6,9]...
  newInterval: [2,7]
  min(1,2)  max(9,7)

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
let len = intervals.length, 
    _result = [],
    i = 0,
    rightChild = 0, // 右侧区间数量
    left = newInterval[0],  // 合并集合的边界
    right = newInterval[1]  // 合并集合的边界

  while(i < len){
    // newInterval 左侧区间
    if(intervals[i][1] < newInterval[0]){
     _result.push(intervals[i])
    }else if(intervals[i][0] > newInterval[1]){
      // newInterval 右侧区间 第一次遍历到右侧区间是添加合并后的区间
      if(rightChild === 0) _result.push([left, right]);
      _result.push(intervals[i]);
      rightChild++
    }else{
      // 存在交集区间
      left = Math.min(left, intervals[i][0]);
      right = Math.max(right, intervals[i][1]);
    }
    i++
  }
  // 如果不存在合右侧区间，即合并后的区间包括了intervals最后的子区间
  // 则须要最后追加合并区间到结果数组中
  if(rightChild === 0) _result.push([left, right]);
  return _result
};