什么时候，贪心选择能够保住最优解？

一间房间收到若干开始和结束时间固定的使用请求，目标是接受尽可能多的请求。假设请求有限、每段时长为正、只有一个资源，并允许下一段恰好在上一段结束时开始。MIT 的区间调度讲义采用了这一相容约定。

贪心规则每次选择当前最早结束的区间，然后只保留开始时间不早于其结束时间的请求。早结束似乎能为后续安排留出空间；交换论证把这一想法变成了有条件的数学保证。

设 g 是最早结束的请求，o 是某个最优安排中的第一个请求。因为 finish(g) ≤ finish(o)，将 o 换成 g 后，所有后续请求仍然可行，已选数量也不变。因此，至少存在一个以 g 开头的最优安排，即使原来的最优安排没有选它。

在 finish(g) 之后，剩余请求仍构成同类问题。最优安排的剩余部分也必须在该子问题中最优：否则，用更多的相容请求替换它，就能改善整个安排。从空集开始归纳，便可反复应用交换步骤，直到没有请求。这一论证覆盖了满足上述条件的所有有限输入。

现在把目标改成总权重。本文构造三个请求：A 占用 [0,2]、权重为 1；B 占用 [2,4]、权重为 1；C 占用 [0,4]、权重为 3。由于允许端点相接，A 与 B 相容。最早结束策略选择 A，再选 B：共两个请求，总权重为 2；只选 C 的权重则为 3。

在这个例子中，A 加 B 对数量目标最优，C 对权重目标最优。交换步骤保留了“一换一”的数量，却未必保留价值。这个反例推翻了加权情形的保证；一般性的交换证明才建立了不加权情形的保证。

目标改变时，应重新检查证明中每一步保留了什么。一个完整的贪心论证需要说明：替换后为什么可行、目标值为何不受损，以及为什么能在更小的问题上继续使用同样的论证。