CSP-S 2025 第一轮 第15题：5 个独立的、不可抢占的任务 A_1, A_2, A_3, A_4, A_5 需

题目

$5$ 个独立的、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3, 4, 2, 5, 1$ 和 $5, 10, 3, 15, 11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

选项

• A. 处理时间最短的任务 $A_5$
• B. 截止时间最早的任务 $A_3$
• C. 处理时间最长的任务 $A_4$
• D. 任意一个任务都可以

答案

B

题解

选 B，优先执行截止时间最早的任务 \(A_3\)。

按截止时间从早到晚排列，执行顺序为 \[ A_3\to A_1\to A_2\to A_5\to A_4。 \]

各任务的完成时刻如下：

所有任务都没有超时，总惩罚为 \(0\)，因此一定最优。

为什么不能先做最短的 \(A_5\)？先做它后，即使立即执行 \(A_3\)、\(A_1\)，\(A_1\) 也要到 \(1+2+3=6\) 时才能完成，超过截止时刻 \(5\)。而先做 \(A_1\)、\(A_2\) 或 \(A_4\)，都会使 \(A_3\) 超时。因此本题必须先做 \(A_3\)。