LeetCode 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 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.sort(function(a,b){
    return a[0]-b[0]
  })

什么时候需要合并？

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

解决包含问题

按上面的方法解决合并新问题就会出现了----可能后一个包含了前一个
【例如 14 23 按上面方法合并就会变成 13的情况但明显不合题意应当是14即前一项不动】
因此在合并前需要进行判断如果后一项的右边界<=前一项右边界就跳过不动反之则进行上述方法合并

代码

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
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++) {
    // 获取结果数组中最后一个区间
    var lastInterval = res[res.length - 1];

    // 如果当前区间的左边界大于结果数组中最后一个区间的右边界，说明它们不重叠
    if (intervals[i][0] > lastInterval[1]) {
      // 不重叠，将当前区间加入结果数组
      res.push(intervals[i]);
    } else if
      // 否则，当前区间与结果数组中最后一个区间有重叠
      // 检查当前区间的右边界是否大于结果数组中最后一个区间的右边界
       (intervals[i][1] > lastInterval[1]) {
        // 如果是，更新结果数组中最后一个区间的右边界
        lastInterval[1] = intervals[i][1];
      }
      // 如果当前区间的右边界不大于结果数组中最后一个区间的右边界，则不需要做任何操作
  }

  // 返回合并后的区间数组
  return res;
};

代码分析

检查输入是否为空：
```
if(intervals.length==0)
  return []
```
如果输入的区间数组intervals为空，那么直接返回一个空数组，因为没有区间需要合并。
初始化结果数组：
```
var res=[]
```
创建一个空数组res，用来存放合并后的区间。
对区间数组进行排序：
```
intervals.sort(function(a,b){
  return a[0]-b[0]
})
```
使用sort方法对intervals数组进行排序，排序的依据是区间的左边界（即start）。这样，我们可以得到一个左边界递增的区间数组。
将第一个区间加入结果数组：
```
res.push(intervals[0])
```
将排序后的第一个区间（即左边界最小的区间）加入到结果数组res中。
遍历剩余的区间：
```
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
```
遍历完成后，返回结果数组res，它包含了所有合并后的不重叠区间。