数据结构与算法 / 系统课时
用区间贪心安排不冲突选择
用区间贪心安排不冲突选择
区间题常把目标包装成会议安排、删除重叠区间或射气球,但核心决策经常相同:如何给后续选择留下尽可能大的空间。本篇从“优先选择结束最早的区间”出发,推导不重叠区间的标准贪心,并说明何时应按右端点排序。
学习目标
- 能把删除重叠区间转化为最大化不冲突区间数量
- 掌握按结束位置排序并线性扫描的区间贪心
- 能用交换论证解释为什么结束最早的可行区间安全
把删除问题改写成选择问题
以 LeetCode 435“无重叠区间”为例,要求删除最少的区间,使剩余区间互不重叠。直接思考“每次删哪个”会产生很多分支,更简单的等价目标是:尽量保留更多互不重叠的区间。
如果总共有 n 个区间,最多能保留 k 个不重叠区间,那么最少删除数就是 n - k。问题由删除决策变成经典区间选择。
关键规则是按右端点从小到大排序。每次遇到与已选区间不冲突的区间就接受它,并把当前结束位置更新为该区间的右端点。

为什么要按右端点排序
假设当前所有可行区间中,贪心选择结束最早的区间 G;某个最优方案第一项却选择了结束更晚的 O。因为 G 的结束时间不晚于 O,把最优方案中的 O 替换成 G 后,原本能排在 O 后面的区间依然能够排在 G 后面。
因此这次交换不会减少后续可选区间数量,也不会降低最终保留数量。于是至少存在一个最优方案以 G 开头,贪心选择是安全的。固定 G 后,对右侧剩余区间继续应用同样规则即可。
这也解释了为什么通常不是按开始时间最早排序。开始得早并不代表释放资源早;一个很早开始但持续很久的区间,反而可能挡住大量短区间。
实现不重叠区间选择
下面直接求最少删除数。排序后只需要维护最后一个已保留区间的结束位置,时间复杂度主要来自排序。
from typing import List
def erase_overlap_intervals(intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda interval: interval[1])
kept = 0
end = float("-inf")
# 只接受起点不早于当前结束位置的区间。
for start, finish in intervals:
if start >= end:
kept += 1
end = finish
return len(intervals) - kept
if __name__ == "__main__":
data = [[1, 2], [2, 3], [3, 4], [1, 3]]
print(erase_overlap_intervals(data))预期输出
1可以保留 [1, 2]、[2, 3]、[3, 4] 三个区间,只需删除 [1, 3]。这里把端点相接视为不重叠,因此判断条件使用 start >= end;如果题目把接触端点也定义为冲突,就要按题意修改边界条件。
区间题先判断目标再排序
“区间题就按右端点排序”同样不是万能公式。排序依据来自目标,而不是数据长得像区间。
当目标是选择最多互不重叠区间、删除最少重叠区间时,结束最早通常是关键,因为它最大化后续剩余空间。LeetCode 452“用最少数量的箭引爆气球”也可以围绕右端点决策:在当前公共可射范围的右侧尽量晚地放箭,从而争取让一支箭覆盖更多后续气球。
而“合并区间”解决的是把所有覆盖范围归并,并不是从候选区间中做舍弃选择。它通常按左端点排序,然后持续扩展当前合并区间的右边界。两类题都需要排序扫描,但贪心变量和证明目标不同。
复杂度与边界
设区间数量为 n。排序需要 O(n log n),随后扫描一次需要 O(n);除排序实现使用的额外空间外,贪心状态只保存计数和一个结束位置。
空输入应返回 0。端点能否相等、区间是闭区间还是半开区间,则必须以题目定义为准。真正需要记住的不是某一行比较符号,而是“用最早释放资源的选择,为后续保留最大可行空间”这一决策原则。