准备过大厂 OD 机考 C 卷的人十有八九刷到过一道叫“执行任务赚积分”的题。这题可以用 Java、Python、JS、C/C、GO 五种语言来写题目名称听起来像业务系统里的激励玩法实际上是一道非常典型的“带截止时间任务调度 贪心 最小堆”算法题。更关键的是机考环境普遍要求双机位在线监考C 卷又是随机抽题抽出来的很多人本来思路清晰一面对冷冰冰的摄像头就容易慌。这篇文章不聊玄学直接拆题题目怎么读懂、为什么最小堆能拿到最优积分、五种语言怎么快速落地、机考实战里有什么隐藏坑。我先说结论这道题表面上看是“安排任务赚积分”实际上考的是你能不能把“时间轴上的调度问题”转化成“带容量的最优选择问题”。很多人卡在“知道要用堆但不知道为什么用堆”这一步。下面我把正确性论证、多语言实现、考试细节全部串起来讲看完可以直接照着写。1. 先认准题目C卷里的“执行任务赚积分”到底长什么样1.1 题面与输入输出约定“执行任务赚积分”的经典题面大致可以这样理解你有一条时间轴时间从 1 开始往后走每个时间单位只能执行一个任务。现在给你一个任务列表列表中每个任务有两个属性最晚执行时间 d以及完成它之后能获得的积分 p。只要在第 d 个时间单位之内包含 d启动并完成积分就能到手一旦超过 d这个任务就再也不能接了。每个任务执行耗时固定为 1 个时间单位。问怎样安排任务顺序能让最终总积分最大。输入格式在多数版本里是这样第一行一个整数 N表示任务数量。接下来 N 行每行两个整数第一个是截止时间 d第二个是积分 p。输出一个整数表示最大总积分。示例输入5 2 10 1 5 3 20 2 15 1 30对应的最优选择是先做截止时间为 1 积分 30 的任务再做截止时间为 2 积分 15 的任务最后做截止时间为 3 积分 20 的任务总积分是 65。数据范围方面机考版本通常把 N 给到 10^5 甚至更大截止时间可以到 10^9积分累加后可能超出 int 范围。所以排序加数组暴力模拟的方式在大数据量下一定会超时这也决定了这道题必须用 O(N log N) 的贪心加堆解法。1.2 隐含前提最容易看漏这里有一个容易被忽略的关键前提每个任务耗时固定为 1 个时间单位。这个条件让问题的复杂度一下子降了下来。如果任务耗时各不相同题目会变成完全不同的建模方式比如带体积的背包或更复杂的调度。考试时不要默认先确认题干里写的是不是“每个任务消耗一个时间单位”。如果写的是“每个任务耗时为其自身时长”先停下来别直接套堆解法。C 卷里最常见的“执行任务赚积分”就是单位耗时版本但出题人偶尔会把条件改写我见过有人在考场上把“耗时 1”当成默认值结果样例都过不了非常可惜。另外还要注意时间起点。大部分版本把截止时间当成时间点截止时间为 1 表示第 1 个时间单位内可以完成。此时堆中元素个数不能超过当前任务的截止时间 d。如果某任务截止时间是 0说明没有可用时间片任务无法完成代码里if heap.size() d这个条件会自然把它过滤掉因为先入堆再发现堆大小超过 0立刻弹出刚入堆的任务相当于没有执行。1.3 变体识别别把区间任务当成这一题执行任务赚积分还有一个常见变体任务带开始时间 start 和结束时间 end做任务需要占用一段完整时间区间这种题一看就会想到区间动态规划或基于结束时间排序的贪心。我之前带人刷题时经常有人把两道题混在一起。区别很好认如果每个任务只给“截止时间”和“积分”没有开始时间约束那就是单位耗时贪心加堆如果题干有start time任务的调度必须落在某个区间内那就不是这一道题。看到后者建议先想动态规划而不是套最小堆。2. 为什么“截止时间排序 最小堆替换”能拿到最优积分2.1 把题目建模成“带容量限制的选任务问题”假设你按截止时间从小到大的顺序依次处理任务处理到某个任务时前面所有任务的截止时间都小于等于当前任务的截止时间。这时候我们可以思考一个问题在“当前截止时间 d”这根时间轴前缀里最多只能安排 d 个任务因为每个任务耗时 1时间单位只有 d 个。于是问题转化为从已经遇到过的任务里选出一批任务使得这批任务的数量不超过各自对应的截止时间限制同时积分总和最大。最小堆在这里的作用就是始终维护“当前前缀下最优的那批任务”。具体策略是这样的按截止时间升序遍历所有任务每遇到一个任务先把它的积分丢进最小堆。然后检查堆的大小是否超过当前任务的截止时间 d。如果超过说明在时间 1 到 d 这个范围内不可能完成这么多任务必须丢掉一个。丢掉哪个丢掉堆里积分最小的那个因为丢掉它对总积分的影响最小。2.2 为什么贪心在这里是对的很多人一看到“丢掉最小积分”就觉得是拍脑袋其实这个策略可以严格证明。先看可行性任何时候堆中任务数量都不超过当前截止时间 d且这些任务都来自截止时间小于等于 d 的任务集合。因为所有任务耗时相同且可以在任意单位时间执行所以这堆任务是能在时间轴前缀内全部排下的。只要按截止时间从早到晚依次填充时间片就能构造出合法调度。再看最优性假设处理完前 k 个任务后堆里保存的是“在截止时间约束下能够达到最大积分”的一组任务。新来一个任务时堆里多了它如果数量没有超限那它直接被保留结果一定不会变差。如果数量超限则说明当前前缀最多只能容纳 d 个任务必须从 d1 个候选任务中淘汰一个。淘汰最小积分值的任务保留其余 d 个积分更大的任务得到的集合一定是在这个前缀下积分和最大的合法集合。用数学归纳法就可以完成整个证明。这个逻辑和经典问题“带截止时间和利润的任务调度”是完全一致的。考试时如果心里没底可以拿一个反例验证任务是 (截止1, 积分2)、(截止2, 积分3)、(截止2, 积分100)。按截止时间排序后依次处理积分2入堆堆大小1积分3入堆堆大小2等于截止2积分100入堆堆大小3大于截止2弹出最小积分2最终留下3和100总积分103。手动排列一下最优也只能做两个任务103 确实是最大值。2.3 手动推演堆的变化过程回到前面给的示例任务列表为 (2,10)、(1,5)、(3,20)、(2,15)、(1,30)。按截止时间排序后变成(1,30) (1,5) (2,15) (2,10) (3,20)开始遍历处理 (1,30)入堆堆中 [30]堆大小 1等于截止时间 1不弹出。处理 (1,5)入堆堆中 [5,30]堆大小 2大于截止时间 1弹出最小元素 5堆中 [30]。处理 (2,15)入堆堆中 [15,30]堆大小 2等于截止时间 2不弹出。处理 (2,10)入堆堆中 [10,15,30]堆大小 3大于截止时间 2弹出最小元素 10堆中 [15,30]。处理 (3,20)入堆堆中 [15,20,30]堆大小 3等于截止时间 3不弹出。最终堆中积分和为 15 20 30 65。整个过程中弹出的是 5 和 10这两个确实是价值最低、最不值得占用时间片的任务。2.4 复杂度分析排序环节是 O(N log N)堆的每次 push 和 pop 都是 O(log N)每个任务最多入堆一次、出堆一次所以堆操作总计 O(N log N)。空间复杂度 O(N)因为堆里最多同时保存 N 个任务。这个复杂度在 N 10^5 甚至 N 10^6 时都能轻松通过。这里有一个小知识点为什么不用大根堆因为大根堆维护的是最大值能帮我们快速取出“当前最好”的任务但在淘汰时我们需要反复丢掉最小值。如果每次排序找最小值复杂度会退化成 O(N^2)。最小堆的堆顶就是最小值淘汰操作才能做到 O(log N)。3. 五种语言实现与笔试易错点3.1 Pythonheapq 的爽与坑Python 的heapq是最省事的因为标准库直接提供最小堆。但要注意heapq没有直接提供sum(heap)前的类型问题以及在大输入量时如果使用sys.stdin.readline一行行读性能没问题如果用嵌套input()在循环里读取数据量一大就会拖慢速度。建议直接用sys.stdin.buffer.read().split()一次性读完。import sys import heapq def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) tasks [] idx 1 for _ in range(n): d int(data[idx]) p int(data[idx 1]) idx 2 tasks.append((d, p)) tasks.sort(keylambda x: x[0]) heap [] for d, p in tasks: heapq.heappush(heap, p) if len(heap) d: heapq.heappop(heap) print(sum(heap)) if __name__ __main__: main()Python 这里最需要注意的一点是sum(heap)前不需要再把堆转成列表heap 本身就是列表但如果积分很大而 Python 的整数没有溢出问题最终答案一定是对的。3.2 JavaPriorityQueue 与读取优化Java 的PriorityQueue默认就是最小堆使用上很顺手。但有两个点容易踩坑第一读取输入时不要用Scanner在循环里逐行读数据量大时Scanner效率偏低。机考环境里最好用BufferedReader加StringTokenizer。第二总积分记得用long否则两个 10^9 级别的积分相加int 直接溢出变成负数输出就错了。import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int[][] tasks new int[n][2]; for (int i 0; i n; i) { st new StringTokenizer(br.readLine()); tasks[i][0] Integer.parseInt(st.nextToken()); tasks[i][1] Integer.parseInt(st.nextToken()); } Arrays.sort(tasks, (a, b) - a[0] - b[0]); PriorityQueueInteger pq new PriorityQueue(); long ans 0; for (int[] t : tasks) { pq.offer(t[1]); ans t[1]; if (pq.size() t[0]) { ans - pq.poll(); } } System.out.println(ans); } }这里我提前维护了ans每次入堆加积分、出堆减积分最终ans就是堆内所有积分之和免去了最后遍历堆的麻烦。3.3 Cpriority_queue 的类型别写错C 的写法最标准但要特别小心priority_queue的默认行为它默认是大根堆而我们需要的恰恰是最小堆所以要传入greaterint和底层容器vectorint。#include iostream #include vector #include algorithm #include queue using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, int tasks(n); for (int i 0; i n; i) { cin tasks[i].first tasks[i].second; } sort(tasks.begin(), tasks.end()); priority_queueint, vectorint, greaterint pq; long long ans 0; for (auto task : tasks) { int d task.first; int p task.second; pq.push(p); ans p; if ((int)pq.size() d) { ans - pq.top(); pq.pop(); } } cout ans endl; return 0; }这里有一个隐蔽的坑pq.size()返回的是size_t是 unsigned long如果你拿它和整型 d 比较当 d 为负数时虽然题目一般会给正数但保险起见会发生隐式类型转换比较结果会出乎意料。所以我在代码里强制转成(int)pq.size()。3.4 JavaScript没有内置堆手写最小堆JavaScript 是五种语言里最麻烦的因为标准库没有提供优先队列。机考环境不一定允许引入第三方库所以必须能手写一个最小堆。很多人一上来就想着每次弹出一个最小元素时用数组sort重新排这在数据量大时一定会超时。class MinHeap { constructor() { this.heap []; } size() { return this.heap.length; } push(val) { this.heap.push(val); this._siftUp(this.heap.length - 1); } pop() { const top this.heap[0]; const last this.heap.pop(); if (this.heap.length 0) { this.heap[0] last; this._siftDown(0); } return top; } _siftUp(i) { while (i 0) { const parent Math.floor((i - 1) / 2); if (this.heap[parent] this.heap[i]) break; [this.heap[parent], this.heap[i]] [this.heap[i], this.heap[parent]]; i parent; } } _siftDown(i) { const n this.heap.length; while (true) { let smallest i; const left 2 * i 1; const right 2 * i 2; if (left n this.heap[left] this.heap[smallest]) smallest left; if (right n this.heap[right] this.heap[smallest]) smallest right; if (smallest i) break; [this.heap[i], this.heap[smallest]] [this.heap[smallest], this.heap[i]]; i smallest; } } } const readline require(readline); const rl readline.createInterface({ input: process.stdin }); let lines []; rl.on(line, (line) lines.push(line.trim())); rl.on(close, () { const n parseInt(lines[0]); const tasks []; for (let i 1; i n; i) { const [d, p] lines[i].split( ).map(Number); tasks.push([d, p]); } tasks.sort((a, b) a[0] - b[0]); const heap new MinHeap(); let ans 0; for (const [d, p] of tasks) { heap.push(p); ans p; if (heap.size() d) { ans - heap.pop(); } } console.log(ans); });手写堆最容易出错的地方是_siftDown时忘记处理左右子节点都为空的情况或者在 swap 后没有正确更新i。我建议平时多练几遍这个模板考场直接默写。注意这里ans使用 JavaScript 的 Number如果累加值超过 2^53会有精度问题但机考数据一般到不了这个量级。3.5 Gocontainer/heap 接口实现细节Go 的container/heap提供了堆算法但它要求你实现一个接口写起来比 Java 和 C 稍微繁琐。很多人第一次写会忘记在Len()、Less()、Swap()之外实现Push和Pop而且Pop()的签名是interface{}需要做类型断言。package main import ( bufio container/heap fmt os sort strconv ) type minHeap []int func (h minHeap) Len() int { return len(h) } func (h minHeap) Less(i, j int) bool { return h[i] h[j] } func (h minHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *minHeap) Push(x interface{}) { *h append(*h, x.(int)) } func (h *minHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[:n-1] return x } type task struct { deadline int score int } func main() { scanner : bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) scanner.Scan() n, _ : strconv.Atoi(scanner.Text()) tasks : make([]task, n) for i : 0; i n; i { scanner.Scan() d, _ : strconv.Atoi(scanner.Text()) scanner.Scan() p, _ : strconv.Atoi(scanner.Text()) tasks[i] task{d, p} } sort.Slice(tasks, func(i, j int) bool { return tasks[i].deadline tasks[j].deadline }) h : minHeap{} heap.Init(h) var ans int64 0 for _, t : range tasks { heap.Push(h, t.score) ans int64(t.score) if h.Len() t.deadline { ans - int64(heap.Pop(h).(int)) } } fmt.Println(ans) }Go 版本有两点要提醒一是heap.Init(h)只对已有切片元素做堆化空堆时可以省略但写上更规范二是scanner.Scan()每次读一个单词配合bufio.ScanWords效率足够不需要自己写字符串切分。3.6 五套代码的统一测试结果我用开头那组示例数据跑过这五个版本结果一致Python 输出 65Java 输出 65C 输出 65JavaScript 输出 65Go 输出 65机考环境一般只要求提交核心逻辑有的平台需要你实现一个类或函数有的需要完整的 main 程序。不管哪种形式核心逻辑就是“排序 最小堆淘汰”。只要这部分正确语言外壳不影响得分。4. 双机位机考环境下的答题实战细节4.1 双机位怎么摆、C卷抽题意味着什么我重点提醒一句在双机位机考里你的一举一动都在摄像头下面代码窗口基本没有外援概率。双机位的常见要求是电脑或笔记本上的摄像头从正面拍摄你本人和屏幕手机或平板从侧后方大约 45 度角拍摄桌面、双手和电脑屏幕。两台设备都要提前充满电最好连上充电线同时保证网络稳定。第一次参加这种考试的人往往折在设备调试上而不是算法上。建议考试前至少提前半小时做一次环境测试手机支架角度、屏幕亮度、麦克风权限、浏览器版本、输入法全部过一遍。不要等到开考了才发现手机熄屏被判定离场。这里说的 C 卷是机考抽题的卷别标识一般机考会有多套卷子随机分配。C 卷不代表绝对是新题或难题只是评价维度里的一个代号。抽到哪套卷子不可控能控制的是把常见题型练熟。执行任务赚积分这种题正好覆盖了贪心、优先队列、排序三个高频考点所以它经常出现在 C 卷里。4.2 编码前的三分钟读题、边界、样例真正进入答题后最先做的不是写代码而是读题。我给自己定的规矩是前三分钟只做三件事明确输入格式是单组还是多组行内分隔符是空格还是逗号。把题目示例手动算一遍确认自己对输出结果的理解没有问题。划出数据范围和边界条件N 是否可能为 0截止时间是否从 1 开始积分是否可能为负数。这三分钟看起来耽误时间其实是在帮你省后面十分钟的返工。尤其是“边界条件”这一项很多题目的隐藏测试点就藏在里面。4.3 统一代码模板与自测用例多语言环境下最好在本地提前存一个快速读入模板。比如 Java 用 BufferedReaderPython 用 sys.stdin.buffer.read().split()C 用 ios::sync_with_stdio(false)。机考编辑器往往没有自动补全这些模板直接默写出来能明显减少低级错误。写完后不要只测样例。我给读者一个自测清单只有一个任务时输出该任务积分。所有任务都能完成时输出所有积分之和。所有任务截止时间都是 1 时只能做积分最大的一个任务。截止时间相同、积分相差很大的任务验证最小堆正确弹出了最低分任务。任务数为 100000 时跑一遍看是否超时。用一个简单例子验证最后一种情况输入三组任务(1,100)、(1,50)、(1,1)。处理第一个任务堆里 [100]处理第二个任务堆大小 2 1弹出 50处理第三个任务堆大小 2 1弹出 1。最终答案是 100。这个测试能直接看出你弹出的是不是最小值。4.4 提交前必须检查的五个点提交之前按顺序过一遍这五个点结果类型是否足够大Java 和 C 用 longGo 用 int64JavaScript 注意 Number 精度。排序方向是否正确按截止时间从小到大不是按积分从大到小。堆类型是否正确C 的greaterint、Java 的默认PriorityQueue都要保证是小根堆。堆大小判断条件heap.size() d而不是。等于 d 时刚好能安排 d 个任务不需要弹出。是否有多余输出调试用的console.log、System.out、cout、fmt.Println全部清干净否则判题系统会当成输出的一部分。这五条看起来琐碎但很多人的分数就丢在这里。特别是第 4 条写反一个符号等于整个逻辑全变味。5. 我刷这道题踩过的坑与扩展思考5.1 最容易出错的三个细节第一个坑是按积分排序而不是按截止时间排序。有些同学想当然地认为“先把积分高的任务安排进去再处理低积分的”如果只按积分排序不处理截止时间的截止约束得到的结果在小样例上可能对但在稍复杂的用例上就会出错。原因很简单积分高的任务如果截止时间很晚可以放到后面做积分低但截止时间早的任务反而应该被优先安排。这个“先做截止时间紧的再考虑积分高低”的直觉正是这道题贪心策略的核心。第二个坑是堆的弹出时机。有人会先把所有任务都放进堆最后再统一判断这是错的。必须在每个任务处理后立刻检查堆大小与截止时间的关系。因为当前任务加入后堆中所有任务的截止时间都不小于当前任务的截止时间此时如果堆已经超了说明这些任务无法全部排下必须立刻淘汰一个而不是等后面再一起算。第三个坑是积分为正但数据非常大的时候忘记用长整型。Python 没有这个问题但 Java 和 C 很容易踩。积分值看着单个不大N 个任务累加起来就爆 int 了。5.2 出题人可能改条件几种变体与应对执行任务赚积分最常考的是单位耗时版本但我也见过出题人做小改动每个任务有自己的耗时 cost 和截止时间 deadline。这时候最简单的贪心堆就不完全适用于所有数据。需要重新思考按截止时间排序后堆里要维护的不仅是积分还有耗时淘汰时不能只看积分最小还要考虑占用的时间成本。一道题就是一个变种现场推导复杂度会高很多。任务带开始时间和结束时间。此时最大积分问题通常用动态规划解按结束时间排序维护一个“到当前时刻为止的最大积分”数组然后做转移。限制总时间 T。如果题目给了一个最大时间范围超过 T 的截止时间直接取 min(d, T)堆大小限制改成 T 更稳妥。这些变体并不一定都出现在 C 卷但掌握“先判断耗时是否为单位时间”这个动作能让你快速确定是不是套已知模板。5.3 如果不会堆有没有替代方案有人会问实在写不出最小堆能不能用排序加数组模拟如果 N 小于等于 1000可以暴力枚举每个时间片塞哪个任务或者按积分从大到小排序再为每个任务找一个空位。这种方案在数据量小的时候能通过但数据量一大就会超时。更现实的方法是用二分答案加贪心验证猜测一个积分阈值检查是否能在截止时间限制内完成足够多的任务。但实现复杂度不低绕一圈最后还是回到堆。所以堆还是要练的。手写堆在 JavaScript 里是必选项在其他语言里是调包思想比较轻松。建议把“排序 小根堆淘汰”这套流程写成肌肉记忆考场上不需要思考就能默写。5.4 对准备机考的整体建议刷题时不要追求数量。执行任务赚积分这一类题本质上考的是数据结构加贪心策略的组合同类题还包括会议室问题、股票类调度问题、带截止时间的任务选择问题。把这一类题集中刷透比散着刷二十道题更有效果。机考准备到后期我习惯把常用模板固定下来读入模板、快速排序模板、最小堆模板全部存在一个本地文件里。虽然机考不能带资料但把模板练到条件反射上考场自然就写出来了。真正的高手不是临场想算法而是把高频模型提前训练成直觉。最后再分享一个小技巧调试这种带优先队列的题可以在本地加一个打印函数把每次入堆、出堆后的堆状态都打出来。纸上推演加机器输出对照能很快发现你弹出的到底是不是最小值。我在实际练习中就是靠这个办法一次抓到了和写反的问题。考场上如果遇到类似困惑别慌先用小样例手算一遍再把思路拉回到“每个时间片只能放一个任务”这个原始定义上通常都能找到症结。