合并区间

题目

以数组 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 <= starti <= endi <= 104

思路

首先将给定二维数组 arr，按照第一个元素，由小到大排序。
取第一个数组的两个元素，作为结果集中的第一个元素 [[start, end]]。
循环 arr,每次将当前 item[0] 和 end 比较：
- 如果 item[0] > end 则说明符合题意的第一个结果已经出现，放入 result 中，继续循环。
- 如果 item[0] <= end && item[1] > end，此时需要更新 end 值为 item[1]

代码：

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  // 先将数组排序，按每个元素第一个数字大小，由小到大进行排序。
    const arr = intervals.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
 
    const result = []; // 声明结果集
    let [start, end] = [arr[0][0], arr[0][1]]; // 取第一个元素的两个值
    for (let i = 1; i < arr.length; i++) {
        if (arr[i][0] > end) {
            /**
             * 如果第 i 个 item 的第一个数字 大于 end ,
             * 那说明已经出现一个结果集合，需要存如 result ,并且更新 start 和 end
             * */
            result.push([start, end]);
            start = arr[i][0];
            end = arr[i][1];
        } else if (arr[i][1] > end) {
            /**
             * 如果第 i 个 item 的第一个数字 小于 end 且 第 i 个 item 的第二个数字 大于 end，
             * 则说明当前 item 和 当前的 [start, end] 可以合并，此时更新 end 值即可。
             * */
            end = arr[i][1];
        }
    }
 
    result.push([start, end]);
    return result;
};

题目

示例 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 <= starti <= endi <= 104

思路

首先将给定二维数组 arr，按照第一个元素，由小到大排序。

取第一个数组的两个元素，作为结果集中的第一个元素 [[start, end]]。

循环 arr,每次将当前 item[0] 和 end 比较：

如果 item[0] > end 则说明符合题意的第一个结果已经出现，放入 result 中，继续循环。
如果 item[0] <= end && item[1] > end，此时需要更新 end 值为 item[1]

代码：

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  // 先将数组排序，按每个元素第一个数字大小，由小到大进行排序。
    const arr = intervals.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
 
    const result = []; // 声明结果集
    let [start, end] = [arr[0][0], arr[0][1]]; // 取第一个元素的两个值
    for (let i = 1; i < arr.length; i++) {
        if (arr[i][0] > end) {
            /**
             * 如果第 i 个 item 的第一个数字 大于 end ,
             * 那说明已经出现一个结果集合，需要存如 result ,并且更新 start 和 end
             * */
            result.push([start, end]);
            start = arr[i][0];
            end = arr[i][1];
        } else if (arr[i][1] > end) {
            /**
             * 如果第 i 个 item 的第一个数字 小于 end 且 第 i 个 item 的第二个数字 大于 end，
             * 则说明当前 item 和 当前的 [start, end] 可以合并，此时更新 end 值即可。
             * */
            end = arr[i][1];
        }
    }
 
    result.push([start, end]);
    return result;
};