算法汇总|博客系列

# 56. 合并区间

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

示例 1:

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

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

• 输入数组长度小于2则直接返回
• 先将所有的数组进行排序：先判断第0项是不是相等的，是的话则判断第1项
• 定义一个res存储结果，定义一个当前的项cur，默认取第0项
• for循环遍历，从第1项开始，比较第1项和cur，判断cur[1]是否小于interval[0]
  • 例如[[1, 3],[2, 6]]，则cur为[1, 3]，interval为[2, 6]，显然cur[1]小于interval[0]则表示可以进行合并，这时候就得把cur[1]重新赋值。
  • 但是赋值的时候要考虑有可能出现[[1,6],[2,4]]，也就是后面区间的第1项可能会比前面区间的第1项小的情况，此时就是包含关系。所以需要比较cur[1]和interval[1]的大小，取大的那个。
  • 而如果前面一个区间的第1项是小于后面区间的第0项的话，就表示这两个区间不能合并，这时候就得把前面一个区间添加到最终的结果中，并且把cur设置成后面一个区间，再往下比较。
• 全部循环完了之后，cur数组是肯定还有值的，所以需要把它添加到最终的结果里面。

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  if (intervals.length < 2) {
    return intervals;
  }
  intervals = intervals.sort((a, b) => {
    return (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
  })
  let res = [],
    cur = intervals[0];
  for (let i = 1; i < intervals.length; i++) {
    let interval = intervals[i];
    if (interval[0] > cur[1]) {
      res.push(cur);
      cur = interval;
    } else {
      cur[1] = Math.max(cur[1], interval[1]);
    }
  }
  res.push(cur);
  return res;
};