前阵子在题库里刷到一道题，题名叫《学习轨迹》，标签只有一个“贪心”。说实话，第一眼看过去我还以为是什么树上拓扑、依赖规划之类的硬核题，结果把题面读完之后发现模型特别干净：有若干个学习任务，每个任务有自己的耗时和截止时间，你要决定做哪些任务、按什么顺序做，最后在“所有任务都不晚于截止时间”的前提下，让完成的任务数量尽可能多，并输出一条合法的完成顺序。这其实就是一道特别典型的“反悔贪心”题，只是包装了一层“学习轨迹”的外壳。这篇博客就把我从读题到推导、证明、写代码、对拍调试的完整过程都记录下来，希望对准备算法竞赛或者面试的朋友有帮助。

1. 问题模型与核心切入思路

1.1 把“学习轨迹”翻译成数学语言

先不急着上手写代码，而是把题目抽象一下。现在有 n 个学习任务，每个任务有两个关键属性：

• 耗时 ( t_i )：做这个任务需要连续占用多少时间；
• 截止时间 ( d_i )：这个任务必须在时刻 ( d_i ) 之前（含）完成。

另外还有一个隐含限制：同一时刻只能做一个任务，任务一旦开始就不能中途停止，必须一次性做完。你可以选择任意多个任务来做，也可以跳过某些任务。目标很简单：在保证每个被选任务都能按时完成的前提下，让完成的任务数量最多。

这里“学习轨迹”其实就是最终的任务完成顺序。比如你决定做任务 A、D、C，那完成顺序可能是 A → D → C，这个顺序就是一条轨迹。题目要求输出这条轨迹，本质上就是要求你给出一个合法的、最优的调度方案。

1.2 为什么固定一个任务集合时，按截止时间排序是最优的

假设你已经决定要做某个任务集合 S，那么 S 里这些任务按什么顺序做最好？答案是：按截止时间从小到大排序。这个结论很关键，是整个贪心策略的地基。

我们用一个简单的交换论证来解释。假设当前有一个执行顺序，其中相邻两个任务 i 和 j 是逆序的，也就是说 ( d_i > d_j )，但任务 i 排在任务 j 前面。这时候把它们的顺序交换一下，不会让任何任务变晚，反而会更好。

设这两个任务开始前的累计耗时为 T。原来的顺序是先 i 后 j，那么：

• i 的完成时刻是 ( T + t_i )；
• j 的完成时刻是 ( T + t_i + t_j )。

因为 j 的截止时间更早，所以风险在于 ( T + t_i + t_j ) 很可能超过 ( d_j )。交换之后变成先 j 后 i：

• j 的完成时刻是 ( T + t_j )，它比原来的 ( T + t_i + t_j ) 小，所以更安全；
• i 的完成时刻是 ( T + t_j + t_i )，它和原来 j 的完成时刻一样，但 i 的截止时间比 j 晚，所以也更容易满足。

所以任意一个存在逆序对的顺序，都可以通过若干次交换变成按截止时间升序的顺序，而且不会破坏任何任务的截止约束。换句话说，对于一个固定的任务集合，按截止时间升序执行就是最优的执行顺序。

这一步想明白之后，问题就从“排列 + 选择”简化成了“只选择任务，选完之后统一按截止时间排序执行”。

1.3 从“选集合”到“逐个加入 + 反悔”

如果只是固定集合，问题已经很简单了，但集合本身需要选择。直接枚举子集是 ( O(2^n) )，完全不可行。我们需要一个能够在扫描过程中不断做决定的方案。

一个很自然的想法是：把所有任务按截止时间从小到大排序，然后从早到晚依次“尝试”加入当前计划。每加入一个新任务，如果发现当前计划超时了，就从已经选中的任务里删掉一个，让计划重新变合法。

这种“先加入、超时了再删掉一个”的做法，就是反悔贪心。它和普通贪心的区别在于：普通贪心一旦决定就不改了，而反悔贪心允许你临时反悔，把之前某个决定撤销掉。关键是：删掉哪一个？这就是《学习轨迹》这道题真正的考点。

2. 贪心策略推导与正确性证明

2.1 扫描过程的核心维护量

假设我们已经把任务按截止时间升序排好了。扫描到第 i 个任务时，维护两个东西：

• now：当前已经选中的所有任务，按截止时间升序执行，最后一个任务完成所需的累计耗时；
• 一个数据结构，用来记录当前已选任务中“耗时最大”的任务。

每遇到一个新任务 i，先不管三七二十一，把它加进计划里，然后让now += t_i。这时候如果now <= d_i，说明新任务排在当前所有已选任务的最末尾，也能在自己的截止时间前完成，所以当前计划合法，继续往下扫描。

如果now > d_i，说明把任务 i 加进来之后，至少有一个任务的完成时间来不及了。这时候必须从当前已选任务中删掉一个。因为任务数量目标是要最大化，删掉一个之后，数量会回到原来的大小，但我们刚刚尝试过“加入一个”，所以总体数量比原来多 0。我们要做的选择，就是删掉哪一个，让剩下的集合对后续扫描最有利。

2.2 超时之后，为什么删“耗时最大”的任务

这是整个贪心算法最核心的判断。不妨想一想：删掉一个任务之后，会发生什么？

第一，已选任务的数量减少 1； 第二，当前累计耗时now会减少被删任务的耗时t。

对于后面的任务来说，它们关心什么？只关心两件事：已经完成了多少个任务，以及当前累计耗时还有多少。累计耗时越小，后面插入新任务的空间就越大。因此，当必须删一个任务时，删除耗时最大的那个任务，可以让now下降得最多，留给后面的余量最大。

但这样会不会损失什么？比如被删掉的那个任务截止时间特别早，后面有一个截止时间更晚的任务被保留了，这会不会导致问题？不会。因为截止时间更早的任务本身在加入时已经验证过合法了，即使删掉它，也不会让其他更早的任务变差；而保留了截止时间更晚的任务，只会在执行顺序上排在更后面，对前面任务的完成时间没有任何影响。反过来，如果删掉一个耗时较小但截止时间较晚的任务，保留耗时最大的任务，那么now下降得少，而且耗时最大的任务还很占地方，显然更不利于后续。

我们还可以从“支配”的角度来理解。当被迫要删一个任务时，我们面临两个候选方案：方案 A 删除耗时最大的任务，方案 B 删除另一个任务。方案 A 和方案 B 的任务数量相同，但方案 A 的累计耗时更小。由于任务都可以按截止时间升序执行，累计耗时更小的方案里，每个任务的完成时刻都不会比另一个方案更晚。也就是说，方案 A 在可行性上支配了方案 B。所以删除耗时最大的任务一定不会比删除其他任务差。

2.3 用“不变量”来总结正确性

上面是直观理解，如果想让自己更安心，可以引入一个不变量来总结。

假设扫描完前 i 个任务之后，算法维护的集合 S 满足：在所有“仅从前 i 个任务中选出、并且能全部按时完成”的集合中，S 的任务数最多；在任务数最多的所有可行集合中，S 的累计耗时最小。

初始时 S 为空，显然满足。加入新任务 i 后，如果直接合法，那么任务数增加 1，达到理论上界，且总耗时是在原最优集合基础上加上 t_i，可以论证它仍然是最小总耗时的集合。如果超时了，说明想在前 i 个任务中实现比当前任务数多 1 的可行集合是不可能成功的；于是我们回到原来的任务数，此时为了保持“任务数最多且总耗时最小”，必须从当前集合中去掉一个任务。去掉耗时最大的任务，得到的集合在同样任务数中总耗时最小，不变量继续成立。

这个不变量成立，意味着算法最终得到的一定是全局最优：任务数量最多，而且在相同数量下累计耗时最小。这也是为什么它比 DP 更高效，但不会比 DP 更差。

2.4 几个容易被忽略的细节

细节一：只检查当前任务的截止时间够不够？

有人会担心：插入新任务后，之前那些截止时间更早的任务会不会被影响？

不会。因为我们始终是按截止时间升序扫描的，新插入的任务在最终执行顺序里一定排在所有已有任务之后。它不会改变前面任何一个任务的开始时间，所以前面任务的完成时刻不会因为新任务的插入而变大。只要新任务自身在它的截止时间前完成，整个集合就合法。

细节二：删掉的可能就是刚加入的任务

如果新任务的耗时特别大，比如 ( t_i > d_i )，那么它一加入就会超时，删除耗时最大的任务时，删除的可能就是它自己。这相当于“尝试加入后立刻放弃”，是完全正常的。这个操作保证了算法不会强行选择一个本身就不可能按时完成的任务。

细节三：全部任务都无法完成怎么办？

极端情况下，可能每个任务单独做都会超时，例如所有任务的 ( t_i > d_i )。那么算法会不断地加入、删自己，最后堆为空，答案为 0。这种情况也要在实现上兼容，输出空轨迹即可。

3. 代码实现与手工模拟

3.1 为什么选大根堆？

我们需要反复拿到当前已选任务中耗时最大的那个，并且还可能随时加入新任务。这个需求恰好是“优先队列”最擅长的。C++ 里可以用priority_queue，默认就是大根堆，堆顶是最大值。Python 里heapq是小根堆，所以存耗时的时候取负数，模拟大根堆。

实现时还要注意一点：题目最后要求输出轨迹，而堆里只能快速拿到最大元素，没有办法按截止时间升序输出所有元素。所以我们需要额外维护一个标记数组，记录哪些任务在最终集合中。最后再按照一开始排好的截止时间顺序扫描一遍，把标记为存活的任务输出，这个顺序就是合法轨迹。

3.2 C++ 参考实现

#include <bits/stdc++.h> using namespace std; struct Task { long long t; // 耗时 long long d; // 截止时间 int id; // 原始编号 }; int main() { int n; cin >> n; vector<Task> tasks(n); for (int i = 0; i < n; i++) { cin >> tasks[i].t >> tasks[i].d; tasks[i].id = i + 1; } // 核心第一步：按截止时间升序排序 sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) { return a.d < b.d; }); // 大根堆：pair<耗时, 编号> priority_queue<pair<long long, int>> pq; vector<char> alive(n + 1, 0); long long now = 0; for (auto &task : tasks) { pq.push({task.t, task.id}); alive[task.id] = 1; now += task.t; if (now > task.d) { auto [mx, id] = pq.top(); pq.pop(); alive[id] = 0; now -= mx; } } vector<int> ans; for (auto &task : tasks) { if (alive[task.id]) { ans.push_back(task.id); } } cout << ans.size() << '\n'; for (int i = 0; i < (int)ans.size(); i++) { cout << ans[i] << (i + 1 == (int)ans.size() ? '\n' : ' '); } return 0; }

这段代码可以直接 AC 常规版本。需要注意now和task.d都用long long，因为耗时和截止时间都可能很大，累加之后很容易超出int的范围。

3.3 Python 参考实现

import heapq def main(): n = int(input()) tasks = [] for i in range(n): t, d = map(int, input().split()) tasks.append((d, t, i + 1)) tasks.sort() # 按截止时间 d 升序 heap = [] # 大根堆：存 (-耗时, 编号) alive = [False] * (n + 1) now = 0 for d, t, idx in tasks: heapq.heappush(heap, (-t, idx)) alive[idx] = True now += t if now > d: neg_t, idx2 = heapq.heappop(heap) alive[idx2] = False now -= -neg_t ans = [idx for _, t, idx in tasks if alive[idx]] print(len(ans)) print(*ans) if __name__ == "__main__": main()

Python 版本里heapq默认是小根堆，所以存-t，取出时再取负得到真实耗时。整体逻辑和 C++ 一致。

3.4 手工模拟一个完整样例

用下面这组数据来走一遍流程：

排序后顺序就是 1、2、3、4、5。

一开始now = 0，堆为空。

处理任务 1：加入，now = 3，3 <= 4，合法。堆里现在是{3}。

处理任务 2：加入，now = 5，5 <= 5，合法。堆里是{3, 2}。

处理任务 3：加入，now = 6，6 <= 6，合法。堆里是{3, 2, 1}。

处理任务 4：加入，now = 10，10 > 7，超时。此时堆顶是任务 4（耗时 4），所以把任务 4 删掉，now = 10 - 4 = 6。堆里剩下{3, 2, 1}。

处理任务 5：加入，now = 8，8 <= 8，合法。堆里现在是{3, 2, 2, 1}。

最终堆中有 4 个任务，分别是任务 1、2、3、5。按截止时间顺序输出就是1 2 3 5。验证一下：

• 任务 1：完成于时刻 3，截止 4，合法；
• 任务 2：完成于时刻 5，截止 5，合法；
• 任务 3：完成于时刻 6，截止 6，合法；
• 任务 5：完成于时刻 8，截止 8，合法。

所以最优轨迹就是 1 → 2 → 3 → 5，答案 4。

这里可以看到，任务 4 虽然截止时间晚，但耗时太长，如果把它留下，就必须删掉任务 1，最终总耗时反而更大。算法选择删除耗时最大的任务，其实是在为后续任务留出更多空间。

4. 常见问题与调试实录

4.1 排序的第二关键字要不要处理？

很多实现里只按截止时间升序排序，相同截止时间的任务顺序任意。这不会影响答案，因为反悔贪心最终选出的集合和数量是一样的。

不过有一个小细节：如果相同截止时间，耗时大的任务放在前面，可能会导致它加入后又立刻被删掉，多一次堆操作；如果把耗时小的放在前面，操作会少一点。但复杂度上都是 (O(n \log n))，差别不大。我有一次在本地对拍时发现两种排序得到的轨迹编号不一样，但答案数量和可行性完全一致，后来想明白是因为存在多个最优解。如果你希望输出稳定，可以在排序时第二关键字按耗时升序或按编号升序，这样轨迹确定。

4.2 为什么扫描时只判断now > d[i]就够了？

这个问题我在学习的时候困惑了很久。因为当前已选任务里可能有截止时间比d[i]更早的任务，如果now变大了，会不会导致那些更早截止的任务超时？

答案是：不会。因为在扫描过程中，已选任务始终按截止时间升序排列，新加入的任务一定排在末尾。更早的任务完成时刻不会因为后面插入新任务而改变。它们在自己被加入的那个时刻已经验证过合法了，所以后续只需要检查新加入的这个最晚截止任务即可。

这个性质是“按截止时间排序”带来的红利。如果一开始没有排序，这里的正确性就不成立了。

4.3 堆空时能不能pop？

代码里只有在now > d[i]时才进入pop，而这时刚刚push了当前任务，所以堆一定不为空。不要在最外层写一个“如果堆非空才 pop”之类的逻辑，那样反而可能掩盖真正的问题。

我见过有人这样写：

if (now > d) { if (!pq.empty()) { ... } }

这个写法虽然不会 RE，但会掩盖一个逻辑漏洞：如果堆是空的，说明之前已经出错了，不该继续往下跑。正确的做法是在该删除的时候堆一定非空，直接pop就好。

4.4 输出轨迹时，“堆里有什么”不等于“顺序是什么”

这是我第一次写这个题时犯的错。我直接把堆里剩下的任务编号pop出来当作轨迹，结果顺序完全乱。因为堆只保证能快速取出最大耗时元素，并不维护截止时间顺序。

正确的输出方式有两种：

• 用alive标记数组，最后再遍历一次按截止时间排好的任务数组，输出存活任务的编号；
• 或者把所有存活任务的编号收集后，重新按照这些任务原来的截止时间排序再输出。

第一种更简单，也更好调试。记住：你维护“当前集合”用的是堆，但输出“轨迹”时要回到有序数组。

4.5 用 DP 对拍验证贪心

为了确保贪心算法不是碰巧过样例，我写了一个 (O(n^2)) 的 DP 用来对拍。

DP 的状态设计：令dp[j]表示“处理完当前前缀，完成 j 个任务所需的最小累计耗时”，并且保证这 j 个任务按截止时间升序排列时都合法。初始dp[0] = 0，其余为无穷大。

按截止时间升序遍历每个任务，对每个任务做反向更新：

vector<long long> dp(n + 1, LLONG_MAX / 4); dp[0] = 0; for (auto &task : tasks) { long long t = task.t, d = task.d; for (int j = n; j >= 1; j--) { if (dp[j - 1] + t <= d) { dp[j] = min(dp[j], dp[j - 1] + t); } } }

最终最大的j满足dp[j] < INF，就是最优任务数。

这个 DP 的理解方式：dp[j - 1]是完成前 j-1 个任务的最小耗时，把当前任务作为第 j 个任务放到底，只要dp[j - 1] + t <= d，就说明它能在截止时间前完成。反向更新保证每个任务最多被选一次。

对拍时随机生成小规模数据，分别跑贪心和 DP，比较答案数量、合法性、以及最终输出轨迹是否确实不超时。跑了几万组之后，我才敢确信这个贪心是对的。

5. 扩展：从“任务数量”到“加权收益”

5.1 带权任务调度的堆解法

《学习轨迹》只要求最大化任务数量。如果把条件改成“每个任务还有一个收益 ( w_i )，目标是总收益最大”，那删除策略就要变了。此时按截止时间排序的思路不变，但超时后要删除的是“收益最小”的任务，而不是耗时最大的任务。

具体做法是维护一个小根堆，堆内存当前已选任务的收益。每次尝试加入新任务，累加总耗时；如果超时，就从堆里弹出收益最小的任务，并从总耗时里减去它的耗时。这样可以保证在相同总耗时限制下，保留的收益尽可能大。这个模型非常经典，很多任务调度题都是它的变体。

5.2 “学习总时长最长”与“数量最多”的差别

如果题目问的不是“最多能完成几个任务”，而是“在合法前提下，最多能累计学习多长时间”，那又是另一种趣味。这时候每个任务的收益就是它的耗时本身。用带权调度的方法，超时时删除收益最小的任务，也就是删除耗时最短的任务。你会发现这个策略和“数量最多”恰好相反：一个努力留下耗时短的任务，一个努力留下耗时长但价值高的任务。

同样是反悔贪心，不同的优化目标导致不同的删除优先级。这个对比非常值得自己推一遍，能加深对“反悔贪心核心在于维护不变量”的理解。

5.3 更进一步的学习建议

如果你把《学习轨迹》吃透了，可以继续看这些方向：

• 带截止时间、耗时和收益的通用调度问题，核心是排序 + 堆；
• 多台机器并行学习的变体，需要用多个堆或者可撤销堆来维护；
• 依赖关系下的学习路径规划，那就要结合拓扑排序、树形 DP 甚至反悔贪心一起考虑。

算法竞赛里很多题都是这样：表面上是“轨迹”“路径”“规划”，剥开之后底层是一个经典模型。学会从题目包装里找到核心矛盾，比背某个特定解法重要得多。

6. 一点个人经验

这种“排序 + 反悔删除”的贪心题，我踩过最多次的坑不是想不到堆，而是没有想清楚“删除哪个”背后的优化目标。只看任务数量时，删除耗时最大；看总收益时，删除收益最小。不要死记，一定要从“删除一个任务后，对后续状态有什么影响”出发去推导。

如果你也正在学贪心，我建议拿到一道调度题先别急着写代码，先回答三个问题：第一，固定选择集合后，最优执行顺序是什么？第二，当前维护的状态里，哪个量决定了后面的可行性？第三，被迫放弃一个任务时，放弃标准应该是什么？这三个问题想明白，代码只是最后一步。

最后分享一个调试小技巧：写对拍的时候，不要只比较答案数量，还要把贪心输出的轨迹真正模拟执行一遍，逐个检查每个任务的完成时间是否小于等于截止时间。很多反悔贪心实现看起来答案对，但轨迹是错的，问题往往出在输出顺序上。用alive标记数组从有序数组里收集答案，是最稳妥的方式。