LeetCode 合并区间

发布于:2024-11-29 ⋅ 阅读:(20) ⋅ 点赞:(0)

题目描述

以数组 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;
};

代码分析

  1. 检查输入是否为空

    if(intervals.length==0)
      return []
    

    如果输入的区间数组intervals为空,那么直接返回一个空数组,因为没有区间需要合并。

  2. 初始化结果数组

    var res=[]
    

    创建一个空数组res,用来存放合并后的区间。

  3. 对区间数组进行排序

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

    使用sort方法对intervals数组进行排序,排序的依据是区间的左边界(即start)。这样,我们可以得到一个左边界递增的区间数组。

  4. 将第一个区间加入结果数组

    res.push(intervals[0])
    

    将排序后的第一个区间(即左边界最小的区间)加入到结果数组res中。

  5. 遍历剩余的区间

    for(var i=1;i<intervals.length;i++){
    

    从第二个区间开始遍历,因为第一个区间已经被加入到结果数组中了。

  6. 判断当前区间是否与结果数组中最后一个区间重叠

    if(intervals[i][0] > res[res.length-1][1])
    

    如果当前区间的左边界大于结果数组中最后一个区间的右边界,说明它们不重叠,那么直接将当前区间加入到结果数组中:

    res.push(intervals[i])
    
  7. 判断当前区间是否需要合并

    else if(intervals[i][1] > res[res.length-1][1])
    

    如果当前区间的左边界小于等于结果数组中最后一个区间的右边界,说明它们有重叠。这时,我们需要检查当前区间的右边界是否大于结果数组中最后一个区间的右边界。如果是,说明当前区间覆盖了结果数组中最后一个区间的一部分或全部,因此我们需要更新结果数组中最后一个区间的右边界为当前区间的右边界:

    res[res.length-1][1] = intervals[i][1]
    
  8. 返回合并后的区间数组

    return res
    

    遍历完成后,返回结果数组res,它包含了所有合并后的不重叠区间。

这段代码的核心思想是先对区间进行排序,然后逐个检查每个区间是否与结果数组中的最后一个区间重叠。如果重叠,就合并它们;如果不重叠,就将当前区间加入到结果数组中。这样,最终得到的结果数组就是所有区间合并后不重叠的区间集合。