原题地址：合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
排序
两个被判定重叠的区间$[a_0,a_1]$和$[b_0,b_1]$，如果$a_0<b_0$，那么一定存在$a_1 \geq b_0$。所以我们只需要将原数组按每个区间的左端点进行排序，然后再依次判断相邻两个区间是否重叠并合并重叠的区间即可。
具体的实现代码如下：
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
const merge1 = function(intervals) {
// 根据左边界排序
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < intervals.length - 1;) {
let j = i + 1;
// 依次合并符合条件的区间
while (j < intervals.length && intervals[j][0] <= intervals[i][1]) {
// 合并后区间的右端点为两者中较大的一个
intervals[i][1] = Math.max(intervals[i][1], intervals[j][1]);
intervals[j] = null; // 被合并的区间置为null
j ++; // 判断下一个区间能不能被合并
}
// 跳过已经被合并的区间
i = j;
}
// 过滤掉标记为null的区间
return intervals.filter(item => item != null);
};
测试：
let start = new Date();
const test = merge1;
console.log(test([[1,3],[2,6],[8,10],[15,18]])); // [ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]
console.log(test([[1,4],[4,5]])); // [ [ 1, 5 ] ]
console.log(new Date().getTime() - start.getTime()); // 10
时间复杂度： 合并需要一次遍历，虽然代码中有两次循环，但是合并操作完成后会跳过被合并的部分，所以实际只进行了一轮遍历。时间复杂度为$O(N)$
空间复杂度： 原地操作，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 14,2019