多机区间调度
有 m 个学生和 n 个任务区间,每个任务至多一人完成,最大化可完成任务数;按结束时间排序并分配给最晚可接的学生。标签 贪心 / 区间 / 调度 / multiset
题目描述
有 个学生和 个任务。第 个任务占用时间区间 。
每个任务至多由一名学生完成;同一名学生的任务时间不能重叠。求最多能完成多少个任务。
,。
题解
把任务按结束时间 升序排序。维护每个学生当前最后一个任务的结束时间,初始为 。
依次处理每个任务 :
- 在所有结束时间不超过 的学生中,选择结束时间最大的一个;
- 若存在,把该学生的结束时间改为 ,答案加一;
- 若不存在,跳过这个任务。
用 multiset 维护所有学生的结束时间。每次查询前驱 ,找到后删除旧值并插入 。
正确性
记 为处理完前 个任务后算法的调度。证明如下不变量:存在一个全局最优调度 ,满足
- 包含 的所有任务;
- 在每个学生上的已选任务与 完全一致;
- 只会额外安排第 个任务。
初始 为空,任取一个最优调度作为 。
处理第 个任务 时:
- 若算法跳过 ,说明 中每个学生的最后一个任务都与 相交。由于 在这些学生上保留了 的任务, 也没有位置放 ,所以令 即可。
- 若算法把 安排到学生 ,则 的结束时间 是所有不超过 的结束时间中最大的。若 已把 安排到 ,直接令 。
- 若 把 安排到另一个学生 ,交换 中“学生 上 之后的任务”和“学生 上 之后的任务”。因为 ,且 从 开始,交换后两边仍不重叠,任务数不变,得到仍最优且把 放在 的 。
- 若 不安排 ,则学生 在 之后的任务中,第一个与 相交的任务记为 ;若不存在这样的 ,就可以直接把 接在 后面,得到比 更大的解,矛盾。把 换成 : 与前面的任务相容,后面的任务从 的结束时间之后开始,而 的结束时间不小于 ,所以也与 相容。任务数不变,得到含 和 的最优调度。
归纳到最后, 只能包含 ,所以 就是最优调度。
复杂度
排序为 ;每个任务在 multiset 中做一次前驱查询、删除和插入,共 。总时间为 ,空间为 。
参考
- 单机版本:区间调度。