✅56. 合并区间

[bazinga-web]

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] 可被视为重叠区间。

[bazinga-web]

解题思路：

1. 对区间进行排序（根据二维数组的第一项进行由大到小排序）
2. 用curr数组记录当前合并的最大区间，遍历数组中的每一个区间，如果当前区间
   的启始位置小于等于curr的终点位置，则可以继续合并，所以合并并更新curr的
   起始和终止位置。如果当前区间的起始位置大于curr的终止位置，无法合并，将
   curr加入到result数组里，并用当前的区间替换curr的值
3. 最后判断当前值的长度是否为0，不为0时也要push进结果数组中（解决最后一项无法push的问题）

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  if (intervals.length < 2) {
    return intervals;
  }
  intervals.sort((a, b) => a[0] - b[0]);
  let currArr = intervals[0],
    result = [];

  for (const interval of intervals) {
    if (currArr[1] >= interval[0]) {
      currArr[1] = Math.max(currArr[1], interval[1]);
    } else {
      result.push(currArr);
      currArr = interval;
    }
  }

  if (currArr.length > 0) {
    result.push(currArr);
  }

  return result;
};

[Ray-56]

• 先排序
• 后遍历对比

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (!intervals.length) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    let res = [intervals[0]];
    for (let 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;
};