Pengjielee's blog

题目

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

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= start(i) <= end(i) <= 104

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/merge-intervals 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

参考代码1：

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  const result = [];

  //对区间的左端点进行排序（升序）
  intervals.sort((a, b) => a[0] - b[0]);

  //第0个区间
  let prev = intervals[0];

  //从第1个区间开始遍历
  for (let i = 1; i < intervals.length; i++) {
    //当前区间
    let curr = intervals[i];
    //如果前一个区间的右端点 >= 当前区间的左端点 
    //如prev=[1,3]，curr=[2,6]
    // 3 >= 2，则合并为[1,6]
    if (prev[1] >= curr[0]) {
      prev[1] = Math.max(curr[1], prev[1]);
    } else {
      // 如prev=[1,2]，curr=[3,4]
      result.push(prev);
      prev = curr;
    }
  }
  //注意此处
  result.push(prev);
  return result;
};

参考代码2：

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  const result = [];
  const len = intervals.length;
  if (len === 0) {
    return result;
  }

  intervals.sort((a, b) => a[0] - b[0]);

  let i = 0;
  while (i < len) {
    let currLeft = intervals[i][0];
    let currRight = intervals[i][1];
    while (i < len - 1 && intervals[i + 1][0] <= currRight) {
      i++;
      currRight = Math.max(intervals[i][1], currRight);
    }
    result.push([currLeft, currRight]);
    i++;
  }
  return result;
};