无重叠区间
🟡 中等题目描述
给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi]。返回需要移除区间的最小数量，使剩余区间互不重叠。
示例 1
输入：intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
输出：1
解释：移除 [1, 3] 后，剩下的区间没有重叠示例 2
输入：intervals = [[1, 2], [1, 2], [1, 2]]
输出：2
解释：需要移除两个 [1, 2] 来使剩下的区间没有重叠提示
1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= starti < endi <= 5 * 10^4
解法
参考答案 (3 个标签)
贪心 排序 O(n log n)
思路
按区间终点排序，每次选择结束最早的区间，这样能给后面的区间留出更多空间。
代码实现
/**
* @param {number[][]} intervals
* @return {number}
*/
function eraseOverlapIntervals(intervals) {
if (intervals.length === 0) return 0;
intervals.sort((a, b) => a[1] - b[1]);
let count = 1;
let end = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
count++;
end = intervals[i][1];
}
}
return intervals.length - count;
}复杂度分析
- 时间复杂度：O(n log n)，排序
- 空间复杂度：O(1)
为什么按终点排序？
按终点排序可以保证每次选择的区间结束最早，给后面的区间留出最大空间，从而保留最多的区间。