3 个条目
先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。
支持区间覆盖和区间内选至多 k 个不相交子段;线段树维护最大/最小子段和,反复取最大子段并取反。
单机非抢先调度中最小化逾期任务数;等价于选最大可准时子集,Moore–Hodgson 用最大堆反悔最长任务。