贪心每次选择当前看起来最有利的候选，并且不再撤销。它正确的前提是：至少存在一个最优解能包含当前选择，且剩余部分仍能用同一规则解决。仅凭几个样例“看起来合理”不足以推出这个性质。
无权区间选择
给定一组半开区间 [start,end)，选择互不重叠的最多区间。半开约定允许一个在时刻2结束，另一个在时刻2开始。按结束时间升序，每次取与已经选中区间兼容的第一个候选。
def select_intervals(intervals):
if any(start >= end for start, end in intervals):
raise ValueError('intervals must satisfy start < end')
ordered = sorted(intervals, key=lambda item: (item[1], item[0]))
chosen = []
last_end = None
for start, end in ordered:
if last_end is None or start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
if __name__ == '__main__':
print(select_intervals([(0, 5), (0, 2), (2, 4), (4, 6)]))
对 [0,5)、[0,2)、[2,4)、[4,6)，算法选择后三个短区间。按最早开始选可能先拿 [0,5)，只剩一个，说明另一个同样直观的规则不正确。
交换一步，再递归到剩余部分
设 g 是所有候选中最早结束的区间，某个最优解的首个区间为 o。把 o 换成 g 不会减少区间数量，因为 g 结束不晚于 o，原来能接在 o 后的区间仍然能接在 g 后。于是存在以 g 开头的最优解。
选定 g 后，只考虑开始时间不早于 g 结束的区间，问题结构不变。反复应用这一论证得到全局最优。排序 O(n log n)，扫描 O(n)，输出之外的额外空间取决于排序副本；本例保留排序后的列表，因此 O(n)。
权重会改变问题
若每个区间有收益，[0,2) 和 [2,4) 各收益1，[0,4) 收益9，最早结束规则只得2，最优收益为9。目标从“最多个数”变为“最大收益”后，交换论证不再保持目标值。可以按结束时间排序，二分寻找兼容前驱，再做动态规划，不能继续套用原规则。
其他常见贪心也各自需要证明。最小生成树依赖割性质；哈夫曼编码利用最低频节点的交换与合并；某些硬币面额允许“先取最大”，另一些不允许。例如面额1、3、4找零6，贪心得4+1+1，而3+3只要两枚。
如何寻找或推翻一个规则
先明确目标与可行条件，再考虑某个局部选择是否能替换最优解中的对应部分。若难以证明，尝试构造小规模冲突：长短区间、相同结束时间、带权候选、负收益、资源上限。对小输入枚举所有子集，能快速找到反例，但枚举本身不能替代一般证明。
练习与面试自查
把需求改为“让所有区间都能安排，最少需要多少间会议室”，说明为什么此时应按开始时间扫描，并用最小堆保存正在使用的结束时间；它与本例的选择目标不同。
面试中应先解释半开区间约定和交换步骤。还要能回答：若要求保留所有最长区间，目标是否改变；相同结束时间能否随意选；带权版本缺少的最优子结构该怎样表达。测试里主动加入错误贪心会失败的输入。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。