CJTX02｜最短任务优先 题解

核心算法

按任务时长从小到大排序。

思路推导

排在越前面的任务会被计入越多次等待时间。时长较短的任务应优先执行。排序后维护已经执行的总时长 prefix：每安排一个新任务，先把 prefix 加入答案，再把该任务时长加入 prefix。

正确性说明

考虑相邻的两个任务，时长分别为 $x$ 和 $y$。如果 $x>y$ 却让 $x$ 在前，那么这两个任务对后续任务的影响相同，但第二个任务会多等待 $x$。交换顺序后只需等待 $y$，等待总和减少 $x-y$。因此最优序列中不存在前长后短的逆序对，任务必须按时长非递减排列。

复杂度

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(n)$。

易错点

• 第一个任务的等待时间是 $0$；
• 不要把完成时间总和与等待时间总和混淆；
• 累加结果使用 long long。