单位时间任务调度
每个任务耗时为 1、有截止期和利润,选择可准时完成的任务使利润最大;按利润降序用并查集找最晚空位。标签 贪心 / 调度 / 拟阵 / 并查集 / 排序
题目描述
有 个任务,第 个任务耗时为 ,截止时间为 ,完成后的利润为 。一次只能执行一个任务,任务从整数时刻开始。若任务在 或之前完成,则获得它的利润。
求能获得的最大总利润。
,,。
题解
一个任务集合 可行,当且仅当把其中任务按截止时间升序排列为
后,对每个 都有 。因为每个任务占一个单位时间,前 个任务必须占据 这些时刻。
可行任务集构成调度拟阵,因此按利润从大到小贪心:能安排就安排,不能安排就跳过。
安排一个截止时间为 的任务时,把它放在不超过 的最晚空位;若不存在空位则跳过。用并查集维护空位:
parent[t]表示不超过 的最大空位;- 初始
parent[t] = t; find(d)返回可用空位;选中后令parent[slot] = find(slot - 1);- 若 ,先把 截到 。
把任务放在最晚空位,会把更早的位置留给截止时间更紧的任务;结合调度拟阵的交换性质,按利润降序的选择是安全的。
与最小逾期任务不同:这里可以选择不做任务,并最大化利润;最小逾期任务要处理所有任务,只最小化逾期数量。
复杂度
排序为 ,并查集为 ,总时间为 ,空间为 。
参考
- 同型题:Luogu P2949 [USACO09OPEN] Work Scheduling。
- 调度拟阵:拟阵 与 贪心选择模型。