わたしの部屋

1. 什么是最短等待时间问题？#

最短等待时间问题（也叫加工顺序问题、调度问题）是贪心算法里的经典问题。

问题的描述是：

有 $n$ 个顾客（或 $n$ 个任务）等待同一台机器（或一个服务窗口）处理。每个任务的加工时间不同。机器一次只能处理一个任务，且不能中断。应该如何安排加工顺序，才能让所有任务的总等待时间最短？

生活映射

想象你只有一个收银台，面前排了一队人结账。每个人买的东西不一样多，结账时间也不同。你想让所有人”等待的总时间”最少，应该让谁先结账？

直觉就是：让买得少、结账快的人先来。买得多的人排在后面，只会让后面的人等更久。

2. 关键概念：等待时间#

要把这个问题讲清楚，先得搞清楚”等待时间”到底怎么算。

设第 $i$ 个被处理的任务加工时间为 $t_i$（下标 $i$ 表示第 $i$ 个被处理的顺序，不是任务的原始编号），那么：

• 第 $1$ 个任务开始就处理，等待时间为 $0$。
• 第 $2$ 个任务要等第 $1$ 个任务处理完，等待时间为 $t_1$。
• 第 $3$ 个任务要等前两个都处理完，等待时间为 $t_1 + t_2$。
• ……
• 第 $i$ 个任务的等待时间为前 $i-1$ 个任务加工时间之和：

所有任务的总等待时间为：

这个双重求和看起来抽象，我们以 $4$ 个任务为例把它展开。

$n=4$ 时，每个任务的等待时间为：

总等待时间就是：

展开并合并同类项：

可以发现一个规律：

• $t_1$ 出现在它后面 3 个任务的等待时间中，所以被计算 $3$ 次；
• $t_2$ 出现在它后面 2 个任务的等待时间中，所以被计算 $2$ 次；
• $t_3$ 出现在它后面 1 个任务的等待时间中，所以被计算 $1$ 次；
• $t_4$ 是最后一个任务，后面没有任务，所以被计算 $0$ 次。

一般地，第 $k$ 个任务会出现在它后面 $n - k$ 个任务的等待时间中，因此它的加工时间 $t_k$ 被计算 $(n - k)$ 次。

所以总等待时间可以统一写成：

这个公式是关键

$W = \sum_{k=1}^{n} (n - k) \cdot t_k$ 说明：排得越靠前（$k$ 越小）的任务，它被计入总等待时间的次数 $(n-k)$ 就越大。要让 $W$ 最小，就应该让 $t_k$ 小的任务占据”被计入次数多”的位置（即靠前的位置），让 $t_k$ 大的任务往后排。

这正是”短任务优先”的数学根源。

3. 贪心策略#

最短等待时间问题的贪心策略是：

按加工时间从小到大排序，让耗时最短的任务先处理。

也就是经典的 最短处理时间优先（Shortest Processing Time first，SPT）规则。

算法步骤：

1. 把所有任务按加工时间从小到大排序。
2. 按这个顺序依次处理。
3. 累加每个任务的等待时间，得到总等待时间 $W$。

实现很简单。

4. 以 4 个任务为例#

假设有 $4$ 个任务，加工时间分别是：

如果按原始顺序处理（不排序）：

总等待时间：

如果按贪心策略，先排序为 $[1, 2, 4, 8]$，再处理：

总等待时间：

对比 $24$ 和 $11$，差距很大。短任务优先让每个排队的任务都少等一会儿，总等待时间少了超过一半。

为什么差距这么大

原始顺序里那个耗时 $8$ 的任务排在第 $3$ 位，把第 $4$ 位的任务”堵”了很久。贪心策略把长任务挪到最后，它不再拖累任何人；而把它前面省下来的时间，让所有早处理的短任务都受益。

5. Java 实现#

实现分两步：先排序，再累加。维护一个”已加工时间累计值 cur”作为下一个任务的等待时间。

1
import java.util.Arrays;
2

3
public class MinWaitingTime {
4

5
    /**
6
     * 返回所有任务的最小总等待时间。
7
     *
8
     * @param times 每个任务的加工时间
9
     * @return 最小总等待时间
10
     */
11
    public static int minWaitingTime(int[] times) {
12
        if (times == null || times.length <= 1) {
13
            // 没有任务或只有一个任务，都不需要等待
14
            return 0;
15
        }
16

17
        // 1. 贪心：按加工时间从小到大排序，短任务优先
18
        Arrays.sort(times);
19

20
        int total = 0; // 总等待时间
21
        int cur = 0;   // 当前累计的加工时间，也就是下一个任务的等待时间
22

23
        // 2. 依次处理，累加每个任务的等待时间
24
        for (int i = 0; i < times.length; i++) {
25
            // 当前任务要等前面所有任务处理完，等待时间就是 cur
26
            total += cur;
27
            // 处理当前任务后，累计时间增加它的加工时间
28
            cur += times[i];
29
        }
30

31
        return total;
32
    }
33

34
    public static void main(String[] args) {
35
        int[] times = {4, 2, 8, 1};
36

37
        int result = minWaitingTime(times);
38
        System.out.println("最小总等待时间：" + result); // 输出 11
39
    }
40
}

运行结果：

1
最小总等待时间：11

代码里两个变量要分清楚：

• cur：已经处理完的任务的总加工时间。下一个任务开始前，它已经等了这么久，所以 cur 也就是下一个任务的等待时间。
• total：把每个任务的等待时间 cur 累加起来，得到所有任务的总等待时间。

循环里的顺序别写反

一定要先 total += cur（累加当前任务的等待时间），再 cur += times[i]（把当前任务的加工时间并入累计值）。如果写反了，相当于把当前任务的加工时间也算进了它自己的等待时间，结果会偏大。

6. 复杂度分析#

• 时间复杂度：$O(n \log n)$，主要来自排序。
• 空间复杂度：$O(\log n)$，即排序所需的栈空间。

排序是 $O(n \log n)$，遍历累加是 $O(n)$，总时间复杂度由排序主导。如果数据范围很小（比如加工时间都是小整数），也可以像 最优装载 那样用计数排序优化到 $O(n + C)$，其中 $C$ 是加工时间的最大值。

7. 拓展：平均等待时间与多机调度#

8. 总结#

最短等待时间问题的核心是：

让加工时间短的任务先处理，加工时间长的任务后处理。

核心内容如下：

• 总等待时间公式 $W = \sum_{k=1}^{n} (n-k) \cdot t_k$ 揭示了本质：靠前位置的系数大，应该配短任务。
• 贪心策略：按加工时间升序排序（SPT 规则）。
• 平均等待时间和总等待时间等价，贪心策略不变。
• 带权重时升级为 WSPT 规则；任务有到达时间或多台机器时问题变难。

口诀：

短的先做长的后，总等最少不用愁；公式一看就明白，大权配小数最优。