435. 无重叠区间

🟠   🔖  贪心 数组 动态规划 排序  🔗 力扣 LeetCode

题目

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 10^4

题目大意

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠。

注意 只在一点上接触的区间是 不重叠的 。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 10^4

解题思路

要使删除的区间数最少，可以从贪心算法的角度出发，优先保留结束时间较早的区间。因为结束时间越早，后续能够选择的区间范围越大，冲突的可能性越小。

1. 排序区间：
   按照区间的结束时间 end 升序排序。

2. 遍历区间：
   逐一遍历区间，记录当前非重叠区间的结束时间。

   • 如果当前区间的开始时间 start 大于等于前一个非重叠区间的结束时间 end，说明它们不重叠，可以保留当前区间，同时更新当前的 end。
   • 如果当前区间与前一个区间重叠，则跳过当前区间（相当于删除它）。

3. 计算结果：
   用总区间数减去保留的区间数，即可得出需要删除的区间数。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是区间的数量，排序的时间复杂度为 O(n log n)，遍历区间的时间复杂度为 O(n)，总时间复杂度为 O(n log n)。
• 空间复杂度：O(1)，只使用了常数个变量，排序为原地排序。

代码

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
	// 按结束时间排序
	intervals.sort((a, b) => a[1] - b[1]);

	let count = 0; // 记录非重叠区间的数量
	let prevEnd = -Infinity; // 初始化为一个不可能的最小值

	for (let [start, end] of intervals) {
		if (start >= prevEnd) {
			// 如果当前区间不重叠，更新 prevEnd
			prevEnd = end;
			count++;
		}
	}

	// 总区间数 - 非重叠区间数 = 需要删除的区间数
	return intervals.length - count;
};

相关题目

题号	标题	题解	标签	难度	力扣
452	用最少数量的箭引爆气球	[✓]	贪心 数组 排序	🟠	🀄️ 🔗
2446	判断两个事件是否存在冲突		数组 字符串	🟢	🀄️ 🔗