Regret Greedy

反悔贪心先接受当前选择；当约束被破坏时，再撤销此前代价最大或收益最小的选择。优先队列通常用来快速找到需要“反悔”的元素。

Pattern

1. 按时间、截止期或其他单调维度排序；
2. 扫描到当前元素时先加入候选集合；
3. 若集合违反容量或可行性约束，删除最不划算的已选元素；
4. 维护当前集合的代价、数量或收益。

典型例子是课程表调度：按截止期排序，把课程时长加入最大堆；若总时长超过当前截止期，就移除时长最长的课程。删除最长课程能为后续留下最多空间，同时不减少已选课程数量。

Correctness Intuition

在处理完前 $i$ 个元素后，维护一个满足约束、数量最优，并且在相同数量下总代价最小的集合。每次超约束时移除最大代价元素，保持这个不变量。正式证明通常使用交换论证或归纳法。

反悔贪心并不是任意回溯。必须说明“删除哪个元素”能保留局部最优不变量；若约束之间存在复杂依赖，可能需要动态规划、匹配或网络流。