Greedy by Maximum or Minimum

“每次取最大/最小”只是候选策略，不是正确性证明。它适用于当前极值选择能够安全地固定，剩余问题仍与原问题同构的场景。

Common Forms

• 每次合并最小的两个代价：Huffman 编码、连接木棍；
• 每次选择结束最早的区间：最大不重叠区间；
• 每次扩展当前最短距离：非负边图上的 Dijkstra；
• 每次保留代价最小的可行集合：反悔贪心。

实现上，静态顺序通常先排序；候选集合动态变化时使用最小堆或最大堆。

Proof Checklist

1. 极值选择后仍存在包含该选择的最优解吗？
2. 能否把任意最优解的第一步交换成贪心选择而不变差？
3. 删除已确定部分后，剩余问题是否保持同样结构？
4. 平局如何处理，会不会影响后续可行性？

找不到交换论证或不变量时，应构造反例，而不是根据样例继续相信直觉。