435. 无重叠区间（中等）

Blind 75 › 435. 无重叠区间（中等）（第 3 章）

题目

给定一个区间数组 intervals，其中 intervals[i] = [start_i, end_i]。请计算：最少删除多少个区间，才能使剩下的所有区间两两互不重叠。

两个区间只要没有公共的内部位置就算“不重叠”；只在端点相接不算重叠。例如 [1,2] 与 [2,3] 可以同时保留。

自造示例：[[1,4],[2,3],[3,5],[5,6]] → 1。删掉 [1,4] 后，剩下的 [2,3]、[3,5]、[5,6] 互不重叠。

约束：区间数 1 ~ 10⁵；每个区间恰含两个整数；-5 × 10⁴ ≤ start < end ≤ 5 × 10⁴。

一句话：先求“最多能留下多少个互不重叠的区间”，答案就是总数减去这个最大保留数。

最直白的做法是枚举每个区间“留”还是“删”，得到全部 2ⁿ 种方案，再逐个检查是否互不重叠，取保留数最大的方案。n 可达 10⁵，指数级做法显然不可行。

换一个角度看两个冲突的区间：若 [s1,e1] 与 [s2,e2] 重叠，且 e1 ≤ e2，那么保留结束更早的 e1，留给后续的空间只多不少。也就是说，发生冲突时，永远优先保留结束最早的那个。

于是把区间按结束时间升序排列，逐个尝试“接”到当前已保留的最后一个区间后面：能接上就保留，接不上就删掉当前这个更晚结束的区间。为什么全局最优？这是经典的区间调度结论：按结束时间最早贪心，能得到最多的互不重叠区间。

注意不能只按起点排序、然后固定保留先出现的区间。例 [[1,100],[2,3],[3,4]]：先保留 [1,100] 会导致删 2 个，而最优是删 [1,100]、保留其余 2 个。关键不在“先来后到”，而在“结束早”。

排序 + 一次扫描：

按 end 升序排序。
维护 prev_end：当前已保留区间的最后一个结束点，初始为足够小的负数。
遍历排序后的区间 [s,e]：若 s ≥ prev_end，说明它与前面保留的区间不重叠，保留并更新 prev_end = e；否则它和最后保留的区间重叠，删除它，不更新 prev_end。
返回 n - keep。

当前区间	prev_end 前	s ≥ prev_end	动作	prev_end 后
[2,3]	-∞	是	保留	3
[1,4]	3	否（1 < 3）	删除	3
[3,5]	3	是（3 ≥ 3）	保留	5
[5,6]	5	是（5 ≥ 5）	保留	6

保留 keep = 3 个，总区间 n = 4，因此最少删除 4 - 3 = 1 个。

下图把上面 4 个步骤串成流程，并逐步演示：

C++ 片段需补全 main() 函数才能运行在实训台打开 →

class Solution {
public:
 int eraseOverlapIntervals(vector<vector<int>&g
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。