华为OD机考这几年热度一直不减，C卷里有一道出现频率相当高的算法题，叫做“单核CPU任务调度”。我印象里每次考完都有人来问：为什么我的用例过了、自测也过了，但提交就是超时？为什么用Scanner读数据会卡？这题其实并不难，但要想一次跑通、满分通过，还是有几个必须想明白的点。这篇就把这道题的完整思路、Java实现、优化经验和考试避坑细节一起拆开讲。

1. 题目全景：单核CPU任务调度到底考什么

1.1 核心需求解析

华为OD机考C卷的“单核CPU任务调度”是一道典型的模拟题。题目大致是这样描述的（不同场次描述略有差异，核心规则不变）：

有一个单核CPU，系统同时收到了若干个任务。每个任务有三个属性：任务编号、任务到达时间、任务需要执行的时间。CPU每次只能执行一个任务，并且执行过程中不被打断，也就是非抢占式调度。当CPU空闲时，它会从当前已经到达但没有执行的任务中，挑选执行时间最短的任务来执行；如果执行时间相同，则选择任务编号更小的那个。

最终要求按照任务真正执行完成的先后顺序，输出任务编号序列。

我第一次看到这类题目时，第一反应是“这不就是短作业优先嘛，排个序不就完了？”如果你也这么想，说明还没抓到题目的精髓。问题的难度不在排一次序，而在于任务不是一开始全部就绪，而是有“到达时间”这个维度。CPU执行任务需要消耗时间，在执行过程中，新的任务会陆续到达。所以单次排序根本无法覆盖整个动态过程，必须模拟时间推进，实时从“已到达任务集合”里选任务。

1.2 输入输出格式与边界条件

虽然每场考试题面描述会有措辞差异，但输入输出格式基本稳定，这里以最常见版本为例，方便你对照练习。

第一行是一个整数N，表示任务总数。接下来N行，每行三个整数，分别表示任务编号id、到达时间start、执行时间cost。任务编号不重复，到达时间可能是乱序的。

输出一行，包含N个整数，就是任务完成的顺序，按题意要求依次输出任务编号。

题目给定的约束通常是：N最大可达10^5到10^6，start和cost取值范围在int范围内。看到这个量级，就要立刻意识到：这题要求时间复杂度至少是O(N log N)，O(N^2)暴力解法必挂。

特别要提醒几个容易被忽略的边界条件：

• 任务到达时间是乱序的，你不能默认第一行是最早到达的任务。
• 两个任务可能同时到达，此时比较规则是cost小的先执行，cost相同则id小的先执行。
• CPU有可能出现持续空闲的情况。比如当前没有任务，而下一个任务还要很久才到，这时需要直接把时间快进到下一个任务的到达时间，而不是一格一格地浪费循环。
• 有任务cost为0的情况（虽然少见），如果一个任务cost为0，那么它到达后瞬间就会执行完毕，接到输出序列里。

1.3 适用人群与学习价值

这道题非常适合用来巩固优先队列（堆）和事件驱动模拟这两块核心知识。如果你正在准备华为OD机考，或者想系统地刷一刷大规模模拟题，这道题无论如何都值得精做。它不但能锻炼你怎么设计比较器，还能帮助你理解“空闲时间跳转”这种在现实调度中极其常见的优化思路。

即便你只是为了应付面试，我也建议把这道题当作模板吃透，因为它的变体非常多。比如把这题改成抢占式调度，把“执行时间最短”改成“优先级最高”，把任务编号换成入队时间，核心框架都还是一样的，只是比较器的判定条件换了一下而已。

2. 核心算法设计：为什么优先队列是正解

2.1 暴力解法为什么不行

很多第一次接触这题的读者会想到一种直观解法：按照到达时间排序后，维护一个当前时间curTime，每执行一个任务，都重新扫描一遍剩余任务，把所有已到达的任务挑出来，再找其中cost最小的。

每执行一个任务，就要把剩余的所有任务扫一遍，总复杂度是O(N^2)。N=10^5时，理论计算量接近10^10，几乎必超时。就算侥幸通过，也只是因为测试数据稀疏，纯属运气。

暴力解法的核心问题在于：它没有“维护一个动态就绪队列”的意识。任务的到达是随着CPU时间流动不断发生的，如果每次都全量扫描，等于抛弃了前面扫描得到的信息。正确做法是把“已经到达、可以执行”的任务集中管理起来，每次需要选择时，直接从这个集合里取最合适的那个。

2.2 优先队列带来的核心优势

优先队列（PriorityQueue）正是为这种场景而生的。它能够在O(log N)时间内插入一个新到达的任务，也能在O(log N)时间内弹出当前“最优”任务。整体执行N个任务，复杂度为O(N log N)。

把维护的重点放在“就绪任务集”上：CPU每处理完一个任务，时间推进到curTime + cost。在这段时间里，所有start <= curTime + cost的任务都需要被加入就绪队列。但注意，我们不能在循环里逐个比较每个任务是否到达，否则又变成O(N^2)。标准做法是先将所有任务按到达时间排序，再用一个指针index指向“下一个尚未到达的任务”，每当curTime变化，就让index往前走，把所有符合条件的新任务一次性offer进优先队列。

这里有一个很容易理解的类比：就好比食堂开餐，排队窗口里已经站好了先来的同学。只要窗口处理完一个人，时间就过去一点。解开一个新窗口（模拟）时，就去队伍里继续往前叫号，把刚过排队线的同学领进“备选窗口”，然后从中选一个饭量最小的人先打饭。如果整个队还没人到，窗口就空着，等下一批人快到点了再继续。

2.3 比较器设计：优先级规则不能写错

优先队列里存的是什么？最自然是存任务对象，而不是只存cost或id。因为弹出任务时你可能还需要记录它的id和cost，如果只存cost，就丢失了任务标识；只存id，又无法比较cost。所以建议定义一个Task类，field包括id、start、cost。

比较器按题目规则来：

PriorityQueue<Task> queue = new PriorityQueue<>((a, b) -> { if (a.cost != b.cost) { return a.cost - b.cost; } return a.id - b.id; });

这里又有两个隐藏陷阱。

第一个陷阱是直接减法的数值溢出。成本cost范围可能覆盖整个int，a.cost - b.cost可能在差值超过int范围时变成错误的正负号。尤其是当a.cost是负数、b.cost是正数时，减法溢出会导致比较器行为异常，极端情况下堆结构都可能崩坏。建议使用Integer.compare(a.cost, b.cost)，或者比较前切换到long。

第二个陷阱是“如果执行时间相同选择任务编号小”的规则。你别小看这一句，很多人写着写着就漏掉id比较。漏掉的后果是：当两个任务cost一样时，输出顺序不稳定，甚至因为PriorityQueue内部堆的性质，输出结果会乱序。真到了机考这种严格比对输出的环境里，直接给你判拒。

2.4 排序与跳转：处理空闲和乱序到达

另外一个关键设计是，初始时不能直接按id或按cost排序，必须先按start升序排序。这个排序的目的是保证在模拟过程中，我们可以用指针单调向后推进，一个个把到达的任务加入优先队列。

那如果curTime已经超过了当前最早任务的start，但我们还没把任务加进去？不要担心，只要在每次需要“往队列里加任务”时执行：

while (index < n && tasks[index].start <= curTime) { queue.offer(tasks[index]); index++; }

只需要执行这个循环，指针就会把从上一个位置开始一直到当前时间点之前的所有新任务全部入队。任务已经按start排好序，因此永远不会漏掉任何任务。

但如果CPU空闲，也就是队列为空，而且当前时间curTime小于下一个任务的start，怎么办？最简单的处理是把curTime直接跳到下一个任务的start，然后继续执行入队操作。跳过这段纯空闲时间，不会影响输出序列，因为这段时间CPU本来就没有可执行任务。

3. Java实现精讲：从建类到边界控制

3.1 Task类和数据读取

首先定义Task类，注意字段类型。id和cost用int，start也用int。但我在前面说过，比较器里不要直接用减法比较，所以这里用long存取也可以，只是输出时转成int。稳妥起见，统一用long存start和cost，这样比较差值时长整型足够大，不会溢出。

输入读取方面，N最大可能到10^6，使用Scanner逐行读取会非常慢，有可能会在性能上拖后腿。我建议使用BufferedReader配合StringTokenizer，或者用自定义的FastScanner。习惯了之后，你会发现读数据再也不是瓶颈。

static class Task { long id; long start; long cost; Task(long id, long start, long cost) { this.id = id; this.start = start; this.cost = cost; } }

读入所有任务后，按start升序排序。如果start相同，可以按id或cost排序，但这一步只是为了让主循环里的指针顺序有意义，start相同的情况下无论怎么排，主循环都会同时把它们入队，所以不影响最终结果。

3.2 主循环：事件驱动不是逐格扫描

整个主循环用非常简洁的事件驱动方式实现。事件就是“一个任务执行完成”。每执行一个任务，就更新一次curTime，并处理新增任务。如果当前队列为空，就快进到下一个任务的start。因为所有任务都按start排好序，所以直接取tasks[index].start。

long curTime = 0; int index = 0; PriorityQueue<Task> queue = new PriorityQueue<>(comparator); List<Long> result = new ArrayList<>(); while (index < n || !queue.isEmpty()) { if (queue.isEmpty() && index < n && curTime < tasks[index].start) { curTime = tasks[index].start; } while (index < n && tasks[index].start <= curTime) { queue.offer(tasks[index]); index++; } Task task = queue.poll(); curTime += task.cost; result.add(task.id); }

这个循环的精髓在于：curTime只在弹出一个任务时增加，并不会因为任务之间的空闲时间而一格一格地增长。也就是说，任务越多，循环次数恰好等于任务个数，不会平白多出几百万次空转。真正做到了O(N log N)。

你可能会有疑问：为什么在poll之后才把新任务入队？事实上，我在循环开头加入新任务时，已经处理到curTime这个时刻了。但任务在CPU执行期间也会不断到达，所以在poll之后，curTime变成了curTime + cost，此时需要在下一次迭代开头，再把这些新到达的任务加入队列。这样设计是完全正确的。

如果某个任务cost为0，poll之后curTime不变，接着下一个迭代会继续从队列里取出（如果有其他等待任务），或者相同start的新任务都会加入，然后继续执行。流程依然稳定，不会死循环，因为每个cost为0的任务也会被queue.poll()弹出并消耗掉。

3.3 完整代码模板

我把经过本地测试的完整代码贴出来。注意我统一用long避免溢出，并使用FastScanner。

import java.io.*; import java.util.*; public class Main { static class Task { long id; long start; long cost; Task(long id, long start, long cost) { this.id = id; this.start = start; this.cost = cost; } } public static void main(String[] args) throws IOException { FastScanner fs = new FastScanner(); int n = fs.nextInt(); Task[] tasks = new Task[n]; for (int i = 0; i < n; i++) { long id = fs.nextLong(); long start = fs.nextLong(); long cost = fs.nextLong(); tasks[i] = new Task(id, start, cost); } Arrays.sort(tasks, (a, b) -> { if (a.start != b.start) { return Long.compare(a.start, b.start); } return Long.compare(a.id, b.id); }); PriorityQueue<Task> queue = new PriorityQueue<>((a, b) -> { if (a.cost != b.cost) { return Long.compare(a.cost, b.cost); } return Long.compare(a.id, b.id); }); long curTime = 0; int idx = 0; StringBuilder sb = new StringBuilder(); while (idx < n || !queue.isEmpty()) { if (queue.isEmpty() && idx < n && curTime < tasks[idx].start) { curTime = tasks[idx].start; } while (idx < n && tasks[idx].start <= curTime) { queue.offer(tasks[idx]); idx++; } Task t = queue.poll(); curTime += t.cost; sb.append(t.id).append(' '); } System.out.println(sb.toString().trim()); } static class FastScanner { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); String next() throws IOException { while (!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } int nextInt() throws IOException { return Integer.parseInt(next()); } long nextLong() throws IOException { return Long.parseLong(next()); } } }

这段代码可以C卷直接提交。唯一需要注意的是，如果题目要求输出后没有额外换行，这里trim()之后输出即可。如果题目要求输出必须有换行，可以改成System.out.println(sb.toString().trim());，这里已经含有换行了。如果你担心sb输出过大会内存溢出，可以改成使用PrintWriter输出到System.out，每次输出一个id即可，效果一样。不过大多数情况下，N=10^6时，StringBuilder大概几十MB，内存通常够用。

3.4 为什么要先poll再更新curTime

有读者会问：为什么不能在加入新任务后再把curTime往前推进？其实也可以，但必须保证加入新任务时使用的curTime是“上一次任务完成之后的时刻”，否则新任务的入队条件就会错位。

举个例子：当前curTime=5，任务A的cost=3，执行完A后，curTime应该变成8。如果在A的while循环之后、更新curTime之前，就把队列中已经存在但start在8之前的新任务加入，这些任务实际上要在8时刻才到达，你提前把它们加入，就可能会导致它们在A执行完之后被优先弹出，但真实世界中它们还没到达。因此必须坚持“先执行一个任务，再更新curTime到新的完成时刻，然后在下一次迭代开头加入这个时间点之前到达的任务”。

这个逻辑极其重要，也是很多同学自测小数据没问题、大数据出错的核心原因。只要确保主循环的顺序严格为“弹出-更新curTime-循环回到开头入队”，就不会出错。

4. 实际测试与边界用例验证

4.1 构造一个标准输入样例

先用最普通的例子验一把。假设有3个任务：

3 1 0 5 2 2 2 3 4 1

模拟一下：curTime=0，队列中只有任务1，所以先执行任务1，完成时间是5。执行期间，任务2在2时刻到达，任务3在4时刻到达。curTime=5时，队列里有task2（cost=2）和task3（cost=1），按cost最小优先，先执行task3，完成时间6。执行task3期间，没有新任务，队列剩task2，最后执行task2。所以输出顺序是：1 3 2。

这个例子可以直观验证你的代码是否遵循了规则的执行顺序。如果输出是1 2 3，说明你把cost从小到大排序后整个直接按排序输出了，忽略了到达时间的动态性。

4.2 空窗跳转与乱序到达的测试

再构造一个有空窗和乱序的用例：

4 2 10 4 1 0 3 4 15 1 3 5 2

排序后任务顺序：1(0,3), 3(5,2), 2(10,4), 4(15,1)。模拟：curTime=0，队列只有1，执行到3；期间3还没到（5>3），队列空，所以curTime跳转到5，把3加入。执行3的任务，cost=2，到7。队列空，curTime跳到10，加入2，执行4时间到14；期间4在15才到，队列空，curTime跳到15，加入4，执行1到16。输出：1 3 2 4。如果你的代码没有跳转逻辑，而是硬等到5时刻才入队，会造成很多无用循环，甚至TLE。

4.3 大N下的性能测试思路

机考没有专门的本地大用例给你测，我建议自己写一个随机生成器，造N=10^5、10^6级别的数据，跑一遍标准解法，观察耗时。一般来说，在Java默认堆内存下，N=10^6时运行时间应该控制在2秒左右，如果超过4秒，就要检查是否有不必要的开箱装箱、打印导致IO阻塞、或比较器里写入了复杂逻辑。

其中最容易出性能问题的是比较器。每次比较都要访问Task对象的三个字段，如果Task类定义成static class并且字段全是long，其实还好。但如果你把任务对象改成数组、或者把队列改成PriorityQueue<long[]>，比较器里每次都要new一个数组，性能就会下降一个量级。我建议直接用类对象，访问字段开销极小。

4.4 出错的典型现象自查

如果你在做题时发现结果不对，可以按下面顺序排查：

• 输出顺序是否是按完成顺序，而不是开始顺序。
• 优先队列比较器是否漏掉了cost相同按id升序。
• 是否在更新curTime之前就把新到达任务加入队列。
• 是否忘记把初始的curTime跳到最早任务开始时间，导致一开始空转。
• 是否使用了int类型且发生了溢出，比如curTime加上cost后超过int上限。

5. 华为OD机考C卷的实战提醒

5.1 双机位环境下的代码提交注意

既然题目写了“双机位C卷”，这里就多聊几句机考本身。现在OD机考很多场次都是双机位远程监考：一个机位对着你的脸，另一个机位对着你面前的桌面和键盘。在这种环境下，你不可能打开本地IDE调试，也不能在考试中途搜索题解。所以日常练习时就要习惯使用在线编辑器，并且把代码写得结构清晰、少依赖IDE自动补全。

C卷题量一般较大，算法题通常控制在2到3道，难度从简单到偏难都有。“单核CPU任务调度”这类模拟题往往处于中间档位，既不是送分题，也不是压轴难题。如果你前面的大题耗时太多，很容易挤占这道题的时间。我的建议是给这道题预留20到30分钟，其中前5分钟读题和分析样例，最后5分钟检查输出格式。

5.2 Java性能优化细节

华为OD机考提交时，Java通常使用的是某固定版本，且对运行时间有严格要求。我实测下来，Scanner读入10^6个整数大约需要几百毫秒到一秒，而BufferedReader配合StringTokenizer只需要几十毫秒。在大数据量题目中，这个差距往往是致命的。

另外，System.out.println逐行输出也很慢。建议把所有结果拼到StringBuilder里，最后一次性输出。如果你担心拼接大字符串OOM，可以改用BufferedWriter分段输出。不过StringBuilder配合toString再输出，在一般情况下足够了。

5.3 常见答题误区汇总

绝大多数人在“单核CPU任务调度”这道题上挂掉的模式，其实就那么几种。我整理成一个速查表，方便你考前快速浏览。

5.4 变体题目如何举一反三

吃透这道题后，建议顺便看看LeetCode 1834“单线程CPU”，它其实就是这道题的英文版变体，只不过排序规则变成了“执行时间相同按入队时间早”。你把比较器改一下就能做出来。

更进一步，如果题目改成允许抢占式调度，也就是高优先级的任务到达后可以把正在执行的低优先级任务打断，那核心逻辑就不一样了。需要维护“当前正在执行的任务剩余时间”，每来一个新任务，都要比较是否打断。这时你可以用一个“剩余执行时间”字段来模拟，也可以用事件点分步推进。这两种做法都是经典操作系统调度模型，对算法能力很有锻炼价值。

另外，如果题目改成多核CPU，比如有m个核，每个核同时可以执行一个任务，那就要用m个优先队列或者一个大小为m的最小堆栈，逻辑会更复杂，但同样是把“选任务”变成了“选核”+“选任务”的两级模拟。

6. 我的做题心得与建议

这道题我前前后后在模拟题单里写过三遍，第一遍用的暴力解，N=10^4时还勉强能跑；第二遍用优先队列，但比较器漏了id，结果撞上考核用例直接错；第三遍才把快读、long、跳转、入队时机全部理清。所以如果你第一次没写对，不用气馁，这题坑是真的多。

我后来给自己定了一个小规矩：凡是同时涉及“到达时间”和“选择规则”的调度模拟题，一律往优先队列上靠。到达时间负责动态入队，选择规则决定比较器，curTime负责驱动事件循环。这三件事一旦分开，思路就会清晰很多。

给准备参加机考的你一个真诚建议：考前至少手写一遍这道题的完整代码，不要依赖IDE的代码补全。因为机考编辑器不会给你那么智能的提示，手写一遍能帮你记住Task类那里有三个字段、比较器怎么写、while循环的进入条件是什么。我自己手写时发现最容易写错的是排序之后的“while (idx < n && tasks[idx].start <= curTime)”这一个条件，漏了等号会导致刚好在curTime时刻到达的任务不被加入，输出顺序立刻坏掉。

如果你在做题过程中遇到更好玩的调度变体，也欢迎多交流。这题虽然只是C卷的一道模拟题，但背后涉及的调度思想，放到真实的进程调度、扩容任务分发场景里，都是一样的套路。把根基打牢，后面的路会顺很多。