leetcode56-合并区间

leetcode 56

思路

排序

本题可以不按照数组的顺序返回，只要最终的结果是没有重复区间的即满足条件，所以我们可以先进行排序
按照每个区间的左边界对区间进行排序。排序的目的是为了确保每个区间的起始位置按照升序排列，这样我们就可以逐个检查是否存在重叠的区间

排序以后可能出现的情况

nums = [[1,2] [3,4]] 这种情况是没有重叠的，不需要合并
nums = [[1,4] [3,5]]
nums. = [[1,5] [3,4]]
后面两种情况是需要进行合并的，当第二项的第一位是小于第一项的第二位的时候，就一定会有重复区间，此时就需要进行合并两项数组，合并以后的第一位毫无疑问取最小的值：第一项的第一位
那么合并后的第二位取什么值呢？合并以后的第二位需要取最大的值，就要判断第一项的第二位和第二项的第二位谁更大

合并重叠区间

排序后，我们可以使用一个新的数组 result 来存储合并后的区间

• 初始化：首先把排序后的第一个区间放入 result 数组中

从第二个区间开始，遍历剩余的区间。如果当前区间的左边界小于等于 result 数组中最后一个区间的右边界，则说明这两个区间有重叠，需要进行合并。合并的方式是更新最后一个区间的右边界为这两个区间的最大右边界

没有重叠：如果当前区间的左边界大于 result 数组中最后一个区间的右边界，说明没有重叠，可以直接将当前区间添加到 result 数组中

遍历完成后，result 数组中存储的就是所有不重叠的区间，最终返回这个结果

实现

/*** 本题关键是intervals不用按照原来题目中的顺序放回，只要结果是恰好覆盖了输入中的所有区间，没有重复的区间范围就可以* @param {number[][]} intervals* @return {number[][]}*/
var merge = function (intervals) {// 按照左边界进行排序intervals.sort((a, b) => a[0] - b[0])let result = [intervals[0]];for (let i = 1; i < intervals.length; i++) {const item = result[result.length - 1]if (item[1] >= intervals[i][0]) {// 有重叠，需要合并item[1] = Math.max(item[1], intervals[i][1])} else {// 无重叠result.push(intervals[i])}}return result
};