贪心
解题思路
本题和 leetcode🧑💻 452. 用最少数量的箭引爆气球 的思路相同；
弓箭的数量就相当于是非交叉区间的数量，
移除的区间数量 = 总区间数 - 弓箭数量；这里要注意：边界相邻不算重合；
图解
复杂度
-
时间复杂度：
O(nlogn)，其中 n 是数组 intervals 的长度，排序的时间复杂度为O(nlogn)，对所有气球进行遍历并计算答案的时间复杂度为O(n)； -
空间复杂度：
O(logn)，即为排序需要使用的栈空间；
代码实现
var eraseOverlapIntervals = function (intervals) {
let arrows = 1; // 初始化箭头数量
// 1. 对气球的起始位置进行排序
intervals.sort((a, b) => a[0] - b[0]);
// 2. 对比气球在 x 轴方向是否有重叠
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= intervals[i - 1][1]) {
// 2-1. 与上一个气球没有重叠
arrows++;
} else {
// 2-2. 与上一个气球重叠，并更新当前气球的右边界（更新右边界的原因：有可能存在 2 个以上的气球重叠）
intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
}
}
return intervals.length - arrows;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 763. 划分字母区间
上一篇
评论
