多机区间调度

有 m 个学生和 n 个任务区间,每个任务至多一人完成,最大化可完成任务数;按结束时间排序并分配给最晚可接的学生。

标签 贪心 / 区间 / 调度 / multiset

题目描述

有 𝑚 个学生和 𝑛 个任务。第 𝑖 个任务占用时间区间 [𝑠𝑖,𝑡𝑖]。

每个任务至多由一名学生完成;同一名学生的任务时间不能重叠。求最多能完成多少个任务。

1≤𝑚≤𝑛≤2×105,0≤𝑠𝑖<𝑡𝑖≤109。

题解

把任务按结束时间 𝑡𝑖 升序排序。维护每个学生当前最后一个任务的结束时间,初始为 −∞。

依次处理每个任务 [𝑠𝑖,𝑡𝑖]:

  • 在所有结束时间不超过 𝑠𝑖 的学生中,选择结束时间最大的一个;
  • 若存在,把该学生的结束时间改为 𝑡𝑖,答案加一;
  • 若不存在,跳过这个任务。

用 multiset 维护所有学生的结束时间。每次查询前驱 ≤𝑠𝑖,找到后删除旧值并插入 𝑡𝑖。

正确性

记 𝑆𝑖 为处理完前 𝑖 个任务后算法的调度。证明如下不变量:存在一个全局最优调度 𝑂𝑖,满足

  • 𝑂𝑖 包含 𝑆𝑖 的所有任务;
  • 𝑂𝑖 在每个学生上的已选任务与 𝑆𝑖 完全一致;
  • 𝑂𝑖 只会额外安排第 𝑖+1,…,𝑛 个任务。

初始 𝑆0 为空,任取一个最优调度作为 𝑂0。

处理第 𝑖+1 个任务 𝐼=[𝑠,𝑡] 时:

  • 若算法跳过 𝐼,说明 𝑆𝑖 中每个学生的最后一个任务都与 𝐼 相交。由于 𝑂𝑖 在这些学生上保留了 𝑆𝑖 的任务,𝑂𝑖 也没有位置放 𝐼,所以令 𝑂𝑖+1=𝑂𝑖 即可。
  • 若算法把 𝐼 安排到学生 𝑘,则 𝑘 的结束时间 𝑒𝑘 是所有不超过 𝑠 的结束时间中最大的。若 𝑂𝑖 已把 𝐼 安排到 𝑘,直接令 𝑂𝑖+1=𝑂𝑖。
  • 若 𝑂𝑖 把 𝐼 安排到另一个学生 𝑘0,交换 𝑂𝑖 中“学生 𝑘 上 𝑆𝑖 之后的任务”和“学生 𝑘0 上 𝑆𝑖 之后的任务”。因为 𝑒𝑘≥𝑒𝑘0,且 𝐼 从 𝑠≥𝑒𝑘 开始,交换后两边仍不重叠,任务数不变,得到仍最优且把 𝐼 放在 𝑘 的 𝑂𝑖+1。
  • 若 𝑂𝑖 不安排 𝐼,则学生 𝑘 在 𝑆𝑖 之后的任务中,第一个与 𝐼 相交的任务记为 𝐽;若不存在这样的 𝐽,就可以直接把 𝐼 接在 𝑘 后面,得到比 𝑂𝑖 更大的解,矛盾。把 𝐽 换成 𝐼:𝐼 与前面的任务相容,后面的任务从 𝐽 的结束时间之后开始,而 𝐽 的结束时间不小于 𝑡,所以也与 𝐼 相容。任务数不变,得到含 𝑆𝑖 和 𝐼 的最优调度。

归纳到最后,𝑂𝑛 只能包含 𝑆𝑛,所以 𝑆𝑛 就是最优调度。

复杂度

排序为 𝑂(𝑛log𝑛);每个任务在 multiset 中做一次前驱查询、删除和插入,共 𝑂(𝑛log𝑚)。总时间为 𝑂(𝑛log𝑛+𝑛log𝑚),空间为 𝑂(𝑛+𝑚)。

参考

源码位置