刷华为机试模拟题刷到第9套的时候，我发现自己最大的障碍已经不是“不会算法”，而是“会算法但模拟不出来”。这道任务调度模拟题就是典型代表——看起来是普通的优先级队列应用，实际动手写的时候，抢占怎么处理、时间怎么推进、空闲期怎么跳，一个比一个容易踩坑。这篇文章就把这道题从头到尾拆开讲清楚，包括完整的AC代码、判断思路和我在真实调试中遇到的那些坑。适合正在刷华为OD机试、校招机试，或者想系统补一下调度模拟类题目的朋友参考。
1. 这道调度题为什么值得单独写一篇
先说结论，华为机试里的编程题虽然每年题目都在变，但“任务调度”这个方向的出现频率一直很高。无论是操作系统里的CPU调度、网络里的报文处理，还是业务系统中的请求排队，本质都是同一套模型。机试题目不会直接写“请你实现一个优先级调度算法”，而是把这些模型包装成业务场景，但底层考察的东西非常固定。
这道题属于典型的“抢占式优先级调度模拟”。它的核心价值在于：第一，它考察的是事件驱动的模拟思维，而不是单纯的排序或者堆应用；第二，它里面藏了好几个不容易一眼看穿的细节，比如“新任务到达时不一定真的需要抢占”“时间是需要跳跃式推进的”“优先级相同时还要比第二关键字”。这些细节恰恰是机试拉开分数的地方。
先把题目完整贴出来。
题目描述
某系统有一个单核CPU，收到N个任务，第i个任务有三个属性：提交时间arrive[i]、执行时长need[i]、优先级prio[i]。数值越大优先级越高。
CPU采用抢占式优先级调度：任何时刻，从“已经提交且尚未完成”的任务中选择优先级最高的执行。若当前正在执行的任务被新提交的更高优先级任务抢占，则暂停执行，保留已完成部分，等待后续恢复。
若优先级相同，则先执行提交时间更早的任务；若仍然相同，则执行编号更小的任务。
模拟上述调度过程，输出每个任务从提交到执行完成的完成时间，以及所有任务的平均周转时间。
周转时间 = 完成时间 - 提交时间。
输入格式
第一行一个整数N（1 ≤ N ≤ 10^5）。
接下来N行，每行三个整数arrive[i]、need[i]、prio[i]（1 ≤ arrive, need, prio ≤ 10^9）。
输出格式
第一行输出N个整数，分别表示第1到第N个任务的完成时间。
第二行输出平均周转时间，保留两位小数。
很多第一次看到这个题的人会下意识说：“这不就是对所有任务按优先级排序，然后从头到尾执行一遍吗？”问题在于任务不是同时到达的，而且支持抢占。这两个条件一加，问题就从静态排序变成了动态模拟。
我们拿一个例子直观感受一下。
假设有3个任务：
| 任务编号 | 提交时间 | 执行时长 | 优先级 |
|---|---|---|---|
| 1 | 0 | 5 | 1 |
| 2 | 1 | 3 | 3 |
| 3 | 2 | 2 | 2 |
如果按普通优先级排序，任务2优先执行，但时间0时任务2还没提交，CPU只能先执行任务1。时间1时任务2提交，它的优先级是3，高于正在执行的任务1的优先级1，于是任务1被抢占，任务2开始执行。任务2执行3个时间单位后完成，时间来到4。此时任务3也已经提交，任务1剩余2个时长，任务3优先级2比任务1高，所以先执行任务3。整个过程是：1执行到1，2执行到5，3执行到6，最后1继续执行到8。
如果忽略了抢占逻辑，直接按优先级排成2、3、1，结果完全不对。这就是为什么这道题不能靠“静态排序”解决。
2. 读题先读数据范围：初步判断算法模型
华为机试有个特点，数据范围往往直接提示了算法复杂度要求。这道题N最大10^5，arrive和need最大10^9，这些数字不是白给的。
如果采用“时间步进”的方式——也就是用一个循环，从时间0开始每走1个时间单位就检查一次就绪队列并选择任务——那么复杂度是O(maxTime)，而maxTime可能达到10^9甚至更高。这个方案在数据小的时候完全可行，但在这里必挂。就算不考虑时间上限，任务数量10^5、每个任务需要被反复检查，也会在时间复杂度上直接爆炸。
正确的方向应该是：复杂度O(N log N)，把时间当作“事件驱动”来推进，而不是一格一格地走。
什么叫事件驱动？就是CPU真正需要做调度决策的时刻只有两种：
- 有新的任务到达
- 当前正在执行的任务执行完毕
在这两个事件之间的时间段里，CPU正在执行的任务不会发生变化，时间可以一次性“快进”过去。这样，算法需要处理的事件总数大约是O(N)级别，每次从优先队列中取出或放入任务都是O(log N)，整体就能控制在百万级运算以内。
优先队列在这里扮演的角色是“就绪任务集合”。每当需要选任务时，从队列顶部取出优先级最高的。抢占发生时，被抢的任务只是把剩余时长改小，然后重新塞回队列。这套思路是调度模拟题的通用套路。
额外说一句，如果是用Python刷题，建议自己实现一个带哈希标记的堆或者直接使用heapq加lazy deletion，因为Python的heapq不直接支持修改堆内元素的优先级。如果是用Java，PriorityQueue可以配合重新offer实现“软更新”。语言不同，实现细节会有差别，后面我会用Java的写法展开，因为华为OD的机试环境对Java的支持非常完善。
3. 从朴素的“时间步进法”到“事件驱动法”
先把错误的暴力思路写出来，知道它哪里错，才能理解优化版本为什么这么设计。
暴力版的核心思想：用一个数组记录每个任务的剩余执行时长，然后循环模拟每一个时间点。
for t = 0; t < maxTime; t++: 把所有arrive == t的任务加入ready队列 if CPU空闲: 从ready中取一个最高优先级任务开始执行 if CPU忙: 如果当前任务没执行完，继续执行1个时间单位 如果有更高优先级任务新到，执行抢占这个思路在逻辑上是对的，但有两个致命问题。
第一个是性能。假设最晚任务提交时间是10^9，那么循环至少要走10^9次，每次还要做优先队列的操作，这显然不可接受。
第二个是边界处理。时间步进法在“抢占”这块特别容易写出bug：当前任务执行到一半被抢占时，剩余时长需要更新；但优先级相同的任务到达时，到底要不要触发抢占？如果两个任务的优先级相同，按题意应该先执行提交时间早的，如果新任务提交时间更晚，即使优先级“相同”，也不能抢占。可是时间步进法如果每到一个新任务就无条件重新调度，就会把“相同优先级”的情况也当作抢占来处理，结果可能与标准答案不一致。
事件驱动法不一样。它把所有能够“加速”的时间段一次性跳过，只处理真正需要调度的事件。核心思路分三步：
第一步，所有任务按提交时间排序。 第二步，维护一个“就绪队列”，里面存放所有已经提交但尚未完成的任务，按优先级、提交时间、编号排序。 第三步，维护当前时间curTime和当前正在执行的任务current。每次循环：
- 先把当前时刻之前所有已提交任务加入就绪队列；
- 如果CPU空闲，从就绪队列取一个任务执行；
- 计算下一个任务到达时间，判断当前任务能否在当前这个“时间窗口”内执行完；
- 如果在执行完之前有新的任务到达，就把时间推进到那个任务到达的时刻，更新当前任务剩余时长，把它放回队列，重新调度；
- 如果当前任务能执行完，就把时间推进到它的完成时刻，记录完成时间，然后继续从队列取新任务。
这里有一个非常关键的推论：只要发生了“任务到达”这个事件，不管新任务优先级是否高于当前任务，都把它加入就绪队列并重新选择一次。注意，是“重新选择”，并不等价于“抢占”。如果重新选择后当前任务仍然是最高优先级，那么CPU继续执行它，效果等同于没有抢占。这样实现更简单，逻辑上也完全符合题意。
有一个容易忽略的地方是“处理空闲期”。如果当前队列为空、CPU空闲，而下一个任务还没到，不能傻傻地一个时间单位一个时间单位地等，直接把curTime跳到下一个任务的提交时间即可。这一步非常关键，不然事件驱动就失去了意义。
4. 完整AC代码与逐段解读
下面给出Java的AC代码。这个写法在华为OD机试环境（JDK 8+）直接可用。
import java.io.*; import java.util.*; public class Main { static class Task { long arrive; long need; long prio; int id; Task(long arrive, long need, long prio, int id) { this.arrive = arrive; this.need = need; this.prio = prio; this.id = id; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); Task[] tasks = new Task[n]; Task[] sorted = new Task[n]; for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); long c = Long.parseLong(st.nextToken()); tasks[i] = new Task(a, b, c, i + 1); sorted[i] = tasks[i]; } // 按提交时间排序，用于顺序扫描待到达的任务 Arrays.sort(sorted, (x, y) -> Long.compare(x.arrive, y.arrive)); // 就绪队列：优先级高优先；其次提交时间早；再次编号小 PriorityQueue<Task> ready = new PriorityQueue<>((x, y) -> { if (x.prio != y.prio) { return Long.compare(y.prio, x.prio); } if (x.arrive != y.arrive) { return Long.compare(x.arrive, y.arrive); } return Integer.compare(x.id, y.id); }); long[] finish = new long[n + 1]; long curTime = 0; int idx = 0; Task current = null; while (idx < n || !ready.isEmpty() || current != null) { // 如果当前没有任务，并且就绪队列为空，直接把时间跳到下一个任务到达 if (current == null && ready.isEmpty() && idx < n) { curTime = Math.max(curTime, sorted[idx].arrive); } // 把curTime之前所有已到达的任务加入就绪队列 while (idx < n && sorted[idx].arrive <= curTime) { ready.offer(sorted[idx]); idx++; } // 当前CPU没有任务就从队列中取一个 if (current == null) { if (ready.isEmpty()) { continue; } current = ready.poll(); } // 下一个任务什么时候到达？ long nextArrive = (idx < n) ? sorted[idx].arrive : Long.MAX_VALUE; if (nextArrive < curTime + current.need) { // 当前任务无法完整执行完，会有一个新任务到达 long gap = nextArrive - curTime; current.need -= gap; curTime += gap; // 当前任务剩余时长放回就绪队列，重新参与调度 ready.offer(current); current = null; } else { // 当前任务可以执行完 curTime += current.need; finish[current.id] = curTime; current = null; } } StringBuilder sb = new StringBuilder(); double total = 0; for (int i = 1; i <= n; i++) { if (i > 1) { sb.append(' '); } sb.append(finish[i]); total += finish[i] - tasks[i - 1].arrive; } System.out.println(sb.toString()); System.out.printf("%.2f%n", total / n); } }逐段说几个关键点。
优先队列的比较器是整个解法的灵魂。这里有个细节：当优先级相同时，按提交时间从早到晚排。提交时间相同的任务，它们的相对顺序在入队时可能不同，但出队时会按编号排，因为比较器最后一级用了id。这保证了结果的唯一性，也符合题目要求。
主循环有一个容易被忽略的continue分支。当current为null且ready为空时，可能是时间还没到下一个任务到达，此时继续循环会导致什么问题？实际上不会，因为上一个if已经把curTime跳到了下一个任务到达时间，所以这里的continue主要用于处理“idx >= n”且队列空且current不为空等理论边界。保留它是为了防御一些极端输入。
还有一个关键点：当新任务到达导致当前任务被“放回队列”时，其实并没有判断新任务的优先级是否真的更高。也就是说，哪怕新任务优先级更低，当前任务也会被先放回队列再重新取出来。这个过程等效于“没发生抢占”——因为当前任务的优先级比新任务高，它放回队列后会被立刻再次弹出。代码简洁了，逻辑也正确，代价只是多一次堆操作。在10^5的数据量下，这个额外开销完全可接受。
最后是越界问题。10^5个任务，每个need最大10^9，总的完成时间可能达到10^14，这已经超过int范围了。所以Task里的arrive、need、prio，以及finish数组和curTime，全部用long。我看到很多人在这道题上卡在类型上，样例能过，一提交大用例就WA，基本都是因为int溢出。
5. 我在机试里踩过的坑：边界用例与易错点
这部分直接列出来，每一条都是我实际调试中遇到过的，不是理论推演。
第一个坑是“优先级相同”的排序处理。最初我写的比较器只比较了优先级，没管提交时间和编号。结果遇到两个任务：任务A（arrive=0, need=8, prio=5），任务B（arrive=1, need=1, prio=5）。如果只看优先级，A先把CPU占了，但B到达后优先级和A相同，按题意不能抢占，A继续执行。这种场景下排序器只比较优先级确实不会出问题。但换一个场景：A（arrive=0, need=1, prio=5），B（arrive=0, need=5, prio=1），C（arrive=1, need=1, prio=5）。A先执行，执行完时B在队列里，此时C也到了，优先级5比B的1高，所以C先执行。到这里也没问题。问题是如果A和B的优先级相同且同时到达，先入队谁会影响结果吗？答案是：只要比较器里写清楚了“优先级相同按到达时间、再按编号”，就不会影响最终结果，因为两任务的总执行时间固定，执行顺序不会改变总时间，只会改变各自的完成时间顺序。而不写第二级、第三级比较，Java的PriorityQueue会按任意顺序返回，结果就成了“随机答案”，这在机试里比WA还难受，因为本地测试偶尔能过，根本无法稳定复现。
第二个坑是“当前任务放回队列”这个操作。一开始我写的逻辑是：只有当新任务优先级真正高于当前任务时才抢占，否则继续执行当前任务。这个逻辑看起来更“精确”，但实现起来要在两个分支里同时维护“当前任务剩余时长”，代码翻倍，还容易漏更新。后来我改成“无脑放回队列再重新选择”，代码量减少，正确率反而高了。这算是一个通用经验：能用“重新选择”代替“精确判断”的场景，尽量用前者。因为重新选择的结果和精确判断的结果是等价的，而且更不容易写错。
第三个坑是空闲期的处理。最开始我没写“时间跳到下一个任务到达”的逻辑，而是在while循环里不断自增curTime，结果小数据能过，大数据直接超时。后来加了那段if (current == null && ready.isEmpty())更新时间，时间复杂度的量级立刻降下来了。这也是事件驱动模拟的核心，类似于操作系统里的“空闲时让出CPU直到下一个中断到来”。
第四个坑是输出格式。第一行输出的是第1个到第N个任务的完成时间，不是按完成顺序输出，而是按任务编号顺序输出。这个翻译错了整个输出就全歪了。我第一版代码就是按完成顺序存的，结果样例怎么都对不上。所以读题时要把“输出哪个序列”看清楚，这种细节在机试里非常容易被忽略。
第五个坑是多个任务同一时刻到达时的处理。比如三个任务都同时到达，进入就绪队列的顺序由sorted数组的遍历决定，而sorted数组按arrive排序，但arrive相同的情况下排序是不稳定的。按理说，同一时刻到达的任务哪个先入队不应该影响最终结果，因为比较器最终会按优先级和编号选出正确的那个。但有一个前提：比较器里必须包含编号这个最底层的判定。如果没写编号，PriorityQueue在同优先级同到达时间时可能随机返回，结果会时对时错。加上编号之后，同优先级同提交时间的任务就有了确定的出队顺序，输出就能稳定复现。
第六个坑是Long.MAX_VALUE的哨兵。在计算nextArrive时，如果idx >= n，说明所有任务都已经到达过了，后续不存在“新任务到达”事件，此时应该给nextArrive赋一个很大的值。用Long.MAX_VALUE没问题，但要注意curTime + current.need可能溢出。好在current.need在进入这个分支前已经被削减过，curTime也不会无限大，最坏情况下curTime和need都在10^14级别，相加远小于Long.MAX_VALUE，所以不会溢出。不过如果用C++，int溢出问题就是真的会踩，Java的long能扛住。
6. 华为机试答题策略：这类题的通用解法框架
刷完这道题之后，我最大的收获是总结出了一套“调度模拟题”的通用解法框架。以后再遇到类似的题，基本可以照着这个框架一步步走。
第一步，识别模型。看到“单核”“多核”“抢占”“调度”“任务队列”这些词，先往优先级调度上靠。描述里如果出现“数值越大越优先”“取优先级最高”这类字眼，那几乎就是优先队列没跑了。
第二步，划分事件。所有调度决策发生的时刻只有两种：新任务到达、当前任务完成。把这两种事件枚举出来，作为时间推进的依据。
第三步，确定队列语义。这个队列里装什么元素、比较器怎么写。这一步会影响整个模拟的正确性和稳定性。
第四步，确定抢占逻辑。抢占不是“每来一个新任务就中断”，而是“每来一个新任务就重新选择一次”。理解了这个等价关系，代码会简单很多。
第五步，处理空闲期。队列空、CPU空、未来还有任务时，直接把时间跳到下一个任务的提交时间。
第六步，注意类型和输出。所有时间相关变量用long，输出按题目要求精确到小数点后几位。
这套框架不仅可以解决“抢占式优先级调度”，还能套到很多变体里。比如华为机试中常出现的“多个CPU核心”的升级版，处理方式是把“单任务current”换成“每个CPU核心一个current”，然后取所有current中的最小完成时间与下一个任务到达时间比较。再比如“任务有依赖关系”的版本，只需要把就绪条件从“已提交”改成“依赖已满足”，配上入度维护就能解决。核心思想不变，变的只是外围条件。
最后说一个我个人的体会。这题我前后写了三个版本：第一个版本是老老实实按时间步进模拟，在自测小数据时一切正常，我在本地甚至没意识到性能问题；第二个版本改成了事件驱动，但偏要在抢占时判断优先级，代码长了不说，还埋了好几个边界bug；第三个版本才改成现在的“放回队列重新选择”写法，一次通过。回头再看，这题的难点其实不在算法本身，而在于对“事件驱动+重新调度”这个抽象模型的理解深度。能把抽象的模型想明白，代码只是水到渠成的事。刷机试刷到后期，拼的已经不是谁见过的题多，而是谁在有限时间内能把题目快速抽象成已知模型。这个能力，只能靠一道题一道题地磨出来。
