对 schedule-with-completion-duration.md 的更简单的解决方案
作者: spike1236创建于 2026年1月29日更新于 2026年3月7日
标签enhancement
对于 schedule-with-completion-duration.md 问题有一个更简单的解决方案。首先,按作业的截止日期对作业进行排序。现在,假设我们选择了一组作业 $S$,计划要完成这些作业,我们的策略是在完成上一个作业后立即开始下一个作业(我们在 $T=0$ 时开始第一个作业)。我们按作业的截止日期从小到大遍历作业,假设我们无法选择当前作业 $i$,因为 $\sum_{j \in S} t_j + t_i > d_i$。然后,我们只需在 $S \cup {i}$ 中(可能是 $i$,这意味着我们跳过它)中删除持续时间最大的作业,然后继续。
内容来源: cp-algorithms/cp-algorithms