为什么贪心算法适用于区间调度？以下是证明
Source: Dev.to
最初发布于 LeetCopilot Blog
TL;DR
- 主题： 使用 最早结束 贪心算法选择最大数量的非重叠区间。
- 为什么重要： 面试会考察你是否能 证明 贪心选择的正确性，而不仅仅是写出一个排序循环。
- 核心步骤：
- 按结束时间对区间进行排序。
- 只遍历一次，保留那些
start ≥ lastEnd的区间。 - 每次选择后更新
lastEnd。
- 常见混淆点： 按开始时间排序或忘记更新
lastEnd边界。 - 你将学到的： 友好的可视化追踪、简短的证明思路、最小代码片段以及练习题。
初学者友好解释：为何选择最早结束的区间
直觉 – 更早结束可以为更多区间腾出空间。选择最早的结束时间留下最大的剩余空间。
交换论证 – 如果你选择了一个比另一个兼容区间结束得更晚的区间，你可以用更早结束的区间替换它，而不会降低答案。（参见文章 Greedy Algorithm Counterexamples for Coding Interviews 中的反例习惯。）
边界跟踪 – 将 lastEnd（上一个被接受区间的结束时间）作为不变式进行维护。
步骤式学习指导
-
按结束时间排序
按开始时间排序是常见的陷阱。按结束时间排序可以保证交换论证成立。 -
遍历一次
对于每个区间，如果start >= lastEnd，则选择它并更新lastEnd。这对应于 Greedy or DP for Coin Change Decisions 中讨论的单调遍历原则。 -
叙述不变式
说：“lastEnd是截至目前已选区间中最早结束的边界。我只接受在它之后开始的区间。” -
用反例检查进行验证
确保没有跳过更早结束且兼容的区间。如果发现，交换仍能保持或增加容量，从而保证正确性。 -
用多样的区间进行练习
使用重叠、嵌套以及结束时间相同的情况，巩固何时进行更新的概念。
可视化示例：追踪表
Intervals (start, end) sorted by end:
[1,2], [2,3], [1,3], [3,4], [2,5]
Pick [1,2] → lastEnd = 2
Pick [2,3] (start >= lastEnd) → lastEnd = 3
Skip [1,3] (starts before lastEnd)
Pick [3,4] → lastEnd = 4
Skip [2,5] (starts before lastEnd)绘制水平条形可以帮助你快速看出兼容性。
代码示例：最早结束贪心
def interval_scheduling(intervals):
# Sort by end time
intervals.sort(key=lambda x: x[1])
chosen = []
last_end = float('-inf')
for start, end in intervals:
if start >= last_end: # compatible?
chosen.append((start, end))
last_end = end
return chosen该代码维护一个单一的边界，并接受在其之后开始的区间，体现了不变式。
实际准备策略
- Swap‑proof rehearsal: 在纸上练习用一分钟解释交换论证。
- Edge‑case drills: 包含结束时间相同和零长度区间的情况。
- Contrast exercises: 尝试按开始时间排序，观察为何会失败；然后再按结束时间排序重复实验。
- Guided review: 像 LeetCopilot 这样的工具可以可视化重叠，并快速显示是否可以更早地交换被跳过的区间。
常见错误避免
| 错误 | 为什么会导致问题 |
|---|---|
| 按开始时间排序 | 当一个早起的区间结束时间较晚时，会错过最优集合，阻碍后续选择。 |
| 意外允许重叠 | 忘记 start >= lastEnd 检查会选择不兼容的区间，破坏最大化。 |
| 误读相等边界 | 决定是否允许相邻区间（end == start），大多数面试题变体是允许的。 |
| 代码解释过多，证明解释不足 | 面试官更关注为什么贪心是安全的，而不是循环本身。 |
常见问题
我如何判断贪心算法是可行的？
如果你能够定义一个局部最优的选择且不会影响后续的容量，并且能够用交换论证来证明它的正确性，那么贪心是有前景的。
在此之前我应该学习什么？
复习基本的排序稳定性，并重新阅读 How to Know When Dynamic Programming Is Needed 中的决策指南，以便与贪心进行对比。
最早结束规则是唯一的吗？
对于最大化区间数量而言，是的；其他排序方式可能会导致容量被阻塞。
我该如何处理带权重的区间？
带权情况需要动态规划；当区间具有不同价值时，简单的贪心算法会失效。
结论
最早结束的贪心算法之所以有效，是因为它每次都锁定可能的最小边界，为后续的选择留下最大的空间。通过演练交换论证、追踪示例，并将 lastEnd 作为不变式，你就能在面试中自信地解释并实现区间调度。
如果你在寻找一个 AI 助手来帮助你掌握 LeetCode 模式并准备面试，快来看看 LeetCopilot！
面试编码时，请访问 LeetCopilot。