第321题(2020-10-09)：leetcode56：合并区间 （字节）

[qappleh]

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

intervals[i][0] <= intervals[i][1] leetcode地址

[qappleh]

分析一下

前提（将数组按左边界排序）--可得到向上递增的数组

 intervals.sort(function(a,b){
    return a[0]-b[0]
  })

什么时候需要合并？

• 当后一项的左边界<=前一项的右边界 即说明有相交 【例如 1~3 2~4 其中2<3所以可以合并】
• 合并方法 只需将后一项的右边界变成前一项的右边界即可 【延续上一个例子 只需将前一项的1~3的3变成后一项的4 即1~4】

解决包含问题

• 按上面的方法解决合并 新问题就会出现了----可能后一个包含了前一个 【例如 1~4 2~3 按上面方法合并就会变成 1~3的情况 但明显不合题意 应当是1~4即前一项不动】

• 因此在合并前需要进行判断 如果后一项的右边界<=前一项右边界 就跳过不动 反之则进行上述方法合并

以下附上全部代码

var merge = function(intervals) {
  if(intervals.length==0)
    return []
  var res=[]
  intervals.sort(function(a,b){
    return a[0]-b[0]
  })
  res.push(intervals[0])
  for(var i=1;i<intervals.length;i++){
    if(intervals[i][0]>res[res.length-1][1])
      res.push(intervals[i])
    else
      if(intervals[i][1]>res[res.length-1][1])
        res[res.length-1][1]=intervals[i][1]
  }
  return res
};