单位时间任务调度

每个任务耗时为 1、有截止期和利润,选择可准时完成的任务使利润最大;按利润降序用并查集找最晚空位。

标签 贪心 / 调度 / 拟阵 / 并查集 / 排序

题目描述

有 𝑛 个任务,第 𝑖 个任务耗时为 1,截止时间为 𝑑𝑖,完成后的利润为 𝑤𝑖。一次只能执行一个任务,任务从整数时刻开始。若任务在 𝑑𝑖 或之前完成,则获得它的利润。

求能获得的最大总利润。

1≤𝑛≤105,1≤𝑑𝑖≤105,1≤𝑤𝑖≤109。

题解

一个任务集合 𝑆 可行,当且仅当把其中任务按截止时间升序排列为

𝑑𝑖1≤…≤𝑑𝑖𝑘,

后,对每个 𝑗=1,…,𝑘 都有 𝑑𝑖𝑗≥𝑗。因为每个任务占一个单位时间,前 𝑗 个任务必须占据 1,…,𝑗 这些时刻。

可行任务集构成调度拟阵,因此按利润从大到小贪心:能安排就安排,不能安排就跳过。

安排一个截止时间为 𝑑 的任务时,把它放在不超过 𝑑 的最晚空位;若不存在空位则跳过。用并查集维护空位:

  • parent[t] 表示不超过 𝑡 的最大空位;
  • 初始 parent[t] = t;
  • find(d) 返回可用空位;选中后令 parent[slot] = find(slot - 1);
  • 若 𝑑>𝑛,先把 𝑑 截到 𝑛。

把任务放在最晚空位,会把更早的位置留给截止时间更紧的任务;结合调度拟阵的交换性质,按利润降序的选择是安全的。

与最小逾期任务不同:这里可以选择不做任务,并最大化利润;最小逾期任务要处理所有任务,只最小化逾期数量。

复杂度

排序为 𝑂(𝑛log𝑛),并查集为 𝑂(𝑛𝛼(𝑛)),总时间为 𝑂(𝑛log𝑛+𝑛𝛼(𝑛)),空间为 𝑂(𝑛)。

参考

源码位置