贪心
解题思路
本题和 leetcode🧑💻 452. 用最少数量的箭引爆气球 的思路相同，都是判断重叠区间的问题；
为了让区间可能的重叠，需要按照区间起始位置对数组进行排序，从前向后遍历区间数组，靠左尽可能让区间重复；
- 获取 当前区间 的范围；
- 如果下一个区间的开始位置还要小于等于当前区间的结束位置，则有重叠，有重叠则要合并，合并后的结束位置应该取两个区间结束位置的最大值，合并后要继续向后判断是否有重叠；
- 将处理完的区间范围放入结果，并更新下一次迭代的索引；
图解
复杂度
-
时间复杂度：
O(nlogn)，其中 n 为区间的数量，排序的开销O(nlogn)，一次线性扫描的开销O(n)； -
空间复杂度：
O(nlogn)，排序需要的空间开销；
代码实现
var merge = function (intervals) {
let res = [];
intervals.sort((a, b) => a[0] - b[0]);
for (let i = 0; i < intervals.length;) {
// 1. 获取 当前区间 的范围
let cur = intervals[i];
// 2. 如果下一个区间的开始位置还要小于等于当前区间的结束位置，则有重叠，有重叠则要合并
let j = i + 1;
while (j < intervals.length && intervals[j][0] <= cur[1]) {
// 2-1. 合并后的结束位置应该取两个区间结束位置的最大值
cur[1] = Math.max(cur[1], intervals[j][1]);
// 2-2. 合并后要继续向后判断是否有重叠
j++;
}
// 3. 将处理完的区间范围放入结果，并更新下一次迭代的索引
res.push(cur);
i = j;
}
return res;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 435. 无重叠区间
上一篇
评论
