华为机试任务调度模拟题：事件驱动+优先队列实现抢占式优先级调度

刷华为机试模拟题刷到第9套的时候我发现自己最大的障碍已经不是“不会算法”而是“会算法但模拟不出来”。这道任务调度模拟题就是典型代表——看起来是普通的优先级队列应用实际动手写的时候抢占怎么处理、时间怎么推进、空闲期怎么跳一个比一个容易踩坑。这篇文章就把这道题从头到尾拆开讲清楚包括完整的AC代码、判断思路和我在真实调试中遇到的那些坑。适合正在刷华为OD机试、校招机试或者想系统补一下调度模拟类题目的朋友参考。1. 这道调度题为什么值得单独写一篇先说结论华为机试里的编程题虽然每年题目都在变但“任务调度”这个方向的出现频率一直很高。无论是操作系统里的CPU调度、网络里的报文处理还是业务系统中的请求排队本质都是同一套模型。机试题目不会直接写“请你实现一个优先级调度算法”而是把这些模型包装成业务场景但底层考察的东西非常固定。这道题属于典型的“抢占式优先级调度模拟”。它的核心价值在于第一它考察的是事件驱动的模拟思维而不是单纯的排序或者堆应用第二它里面藏了好几个不容易一眼看穿的细节比如“新任务到达时不一定真的需要抢占”“时间是需要跳跃式推进的”“优先级相同时还要比第二关键字”。这些细节恰恰是机试拉开分数的地方。先把题目完整贴出来。题目描述某系统有一个单核CPU收到N个任务第i个任务有三个属性提交时间arrive[i]、执行时长need[i]、优先级prio[i]。数值越大优先级越高。CPU采用抢占式优先级调度任何时刻从“已经提交且尚未完成”的任务中选择优先级最高的执行。若当前正在执行的任务被新提交的更高优先级任务抢占则暂停执行保留已完成部分等待后续恢复。若优先级相同则先执行提交时间更早的任务若仍然相同则执行编号更小的任务。模拟上述调度过程输出每个任务从提交到执行完成的完成时间以及所有任务的平均周转时间。周转时间 完成时间 - 提交时间。输入格式第一行一个整数N1 ≤ N ≤ 10^5。接下来N行每行三个整数arrive[i]、need[i]、prio[i]1 ≤ arrive, need, prio ≤ 10^9。输出格式第一行输出N个整数分别表示第1到第N个任务的完成时间。第二行输出平均周转时间保留两位小数。很多第一次看到这个题的人会下意识说“这不就是对所有任务按优先级排序然后从头到尾执行一遍吗”问题在于任务不是同时到达的而且支持抢占。这两个条件一加问题就从静态排序变成了动态模拟。我们拿一个例子直观感受一下。假设有3个任务任务编号提交时间执行时长优先级105121333222如果按普通优先级排序任务2优先执行但时间0时任务2还没提交CPU只能先执行任务1。时间1时任务2提交它的优先级是3高于正在执行的任务1的优先级1于是任务1被抢占任务2开始执行。任务2执行3个时间单位后完成时间来到4。此时任务3也已经提交任务1剩余2个时长任务3优先级2比任务1高所以先执行任务3。整个过程是1执行到12执行到53执行到6最后1继续执行到8。如果忽略了抢占逻辑直接按优先级排成2、3、1结果完全不对。这就是为什么这道题不能靠“静态排序”解决。2. 读题先读数据范围初步判断算法模型华为机试有个特点数据范围往往直接提示了算法复杂度要求。这道题N最大10^5arrive和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不直接支持修改堆内元素的优先级。如果是用JavaPriorityQueue可以配合重新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)); // 就绪队列优先级高优先其次提交时间早再次编号小 PriorityQueueTask 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. 我在机试里踩过的坑边界用例与易错点这部分直接列出来每一条都是我实际调试中遇到过的不是理论推演。第一个坑是“优先级相同”的排序处理。最初我写的比较器只比较了优先级没管提交时间和编号。结果遇到两个任务任务Aarrive0, need8, prio5任务Barrive1, need1, prio5。如果只看优先级A先把CPU占了但B到达后优先级和A相同按题意不能抢占A继续执行。这种场景下排序器只比较优先级确实不会出问题。但换一个场景Aarrive0, need1, prio5Barrive0, need5, prio1Carrive1, need1, prio5。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所以不会溢出。不过如果用Cint溢出问题就是真的会踩Java的long能扛住。6. 华为机试答题策略这类题的通用解法框架刷完这道题之后我最大的收获是总结出了一套“调度模拟题”的通用解法框架。以后再遇到类似的题基本可以照着这个框架一步步走。第一步识别模型。看到“单核”“多核”“抢占”“调度”“任务队列”这些词先往优先级调度上靠。描述里如果出现“数值越大越优先”“取优先级最高”这类字眼那几乎就是优先队列没跑了。第二步划分事件。所有调度决策发生的时刻只有两种新任务到达、当前任务完成。把这两种事件枚举出来作为时间推进的依据。第三步确定队列语义。这个队列里装什么元素、比较器怎么写。这一步会影响整个模拟的正确性和稳定性。第四步确定抢占逻辑。抢占不是“每来一个新任务就中断”而是“每来一个新任务就重新选择一次”。理解了这个等价关系代码会简单很多。第五步处理空闲期。队列空、CPU空、未来还有任务时直接把时间跳到下一个任务的提交时间。第六步注意类型和输出。所有时间相关变量用long输出按题目要求精确到小数点后几位。这套框架不仅可以解决“抢占式优先级调度”还能套到很多变体里。比如华为机试中常出现的“多个CPU核心”的升级版处理方式是把“单任务current”换成“每个CPU核心一个current”然后取所有current中的最小完成时间与下一个任务到达时间比较。再比如“任务有依赖关系”的版本只需要把就绪条件从“已提交”改成“依赖已满足”配上入度维护就能解决。核心思想不变变的只是外围条件。最后说一个我个人的体会。这题我前后写了三个版本第一个版本是老老实实按时间步进模拟在自测小数据时一切正常我在本地甚至没意识到性能问题第二个版本改成了事件驱动但偏要在抢占时判断优先级代码长了不说还埋了好几个边界bug第三个版本才改成现在的“放回队列重新选择”写法一次通过。回头再看这题的难点其实不在算法本身而在于对“事件驱动重新调度”这个抽象模型的理解深度。能把抽象的模型想明白代码只是水到渠成的事。刷机试刷到后期拼的已经不是谁见过的题多而是谁在有限时间内能把题目快速抽象成已知模型。这个能力只能靠一道题一道题地磨出来。