前陣子在題庫里刷到一道題題名叫《學習軌跡》標簽只有一個“貪心”。說實話第一眼看過去我還以為是什么樹上拓撲、依賴規(guī)劃之類的硬核題結(jié)果把題面讀完之后發(fā)現(xiàn)模型特別干凈有若干個學習任務(wù)每個任務(wù)有自己的耗時和截止時間你要決定做哪些任務(wù)、按什么順序做最后在“所有任務(wù)都不晚于截止時間”的前提下讓完成的任務(wù)數(shù)量盡可能多并輸出一條合法的完成順序。這其實就是一道特別典型的“反悔貪心”題只是包裝了一層“學習軌跡”的外殼。這篇博客就把我從讀題到推導、證明、寫代碼、對拍調(diào)試的完整過程都記錄下來希望對準備算法競賽或者面試的朋友有幫助。1. 問題模型與核心切入思路1.1 把“學習軌跡”翻譯成數(shù)學語言先不急著上手寫代碼而是把題目抽象一下。現(xiàn)在有 n 個學習任務(wù)每個任務(wù)有兩個關(guān)鍵屬性耗時 ( t_i )做這個任務(wù)需要連續(xù)占用多少時間截止時間 ( d_i )這個任務(wù)必須在時刻 ( d_i ) 之前含完成。另外還有一個隱含限制同一時刻只能做一個任務(wù)任務(wù)一旦開始就不能中途停止必須一次性做完。你可以選擇任意多個任務(wù)來做也可以跳過某些任務(wù)。目標很簡單在保證每個被選任務(wù)都能按時完成的前提下讓完成的任務(wù)數(shù)量最多。這里“學習軌跡”其實就是最終的任務(wù)完成順序。比如你決定做任務(wù) A、D、C那完成順序可能是 A → D → C這個順序就是一條軌跡。題目要求輸出這條軌跡本質(zhì)上就是要求你給出一個合法的、最優(yōu)的調(diào)度方案。1.2 為什么固定一個任務(wù)集合時按截止時間排序是最優(yōu)的假設(shè)你已經(jīng)決定要做某個任務(wù)集合 S那么 S 里這些任務(wù)按什么順序做最好答案是按截止時間從小到大排序。這個結(jié)論很關(guān)鍵是整個貪心策略的地基。我們用一個簡單的交換論證來解釋。假設(shè)當前有一個執(zhí)行順序其中相鄰兩個任務(wù) i 和 j 是逆序的也就是說 ( d_i d_j )但任務(wù) i 排在任務(wù) j 前面。這時候把它們的順序交換一下不會讓任何任務(wù)變晚反而會更好。設(shè)這兩個任務(wù)開始前的累計耗時為 T。原來的順序是先 i 后 j那么i 的完成時刻是 ( T t_i )j 的完成時刻是 ( T t_i t_j )。因為 j 的截止時間更早所以風險在于 ( T t_i t_j ) 很可能超過 ( d_j )。交換之后變成先 j 后 ij 的完成時刻是 ( T t_j )它比原來的 ( T t_i t_j ) 小所以更安全i 的完成時刻是 ( T t_j t_i )它和原來 j 的完成時刻一樣但 i 的截止時間比 j 晚所以也更容易滿足。所以任意一個存在逆序?qū)Φ捻樞蚨伎梢酝ㄟ^若干次交換變成按截止時間升序的順序而且不會破壞任何任務(wù)的截止約束。換句話說對于一個固定的任務(wù)集合按截止時間升序執(zhí)行就是最優(yōu)的執(zhí)行順序。這一步想明白之后問題就從“排列 選擇”簡化成了“只選擇任務(wù)選完之后統(tǒng)一按截止時間排序執(zhí)行”。1.3 從“選集合”到“逐個加入 反悔”如果只是固定集合問題已經(jīng)很簡單了但集合本身需要選擇。直接枚舉子集是 ( O(2^n) )完全不可行。我們需要一個能夠在掃描過程中不斷做決定的方案。一個很自然的想法是把所有任務(wù)按截止時間從小到大排序然后從早到晚依次“嘗試”加入當前計劃。每加入一個新任務(wù)如果發(fā)現(xiàn)當前計劃超時了就從已經(jīng)選中的任務(wù)里刪掉一個讓計劃重新變合法。這種“先加入、超時了再刪掉一個”的做法就是反悔貪心。它和普通貪心的區(qū)別在于普通貪心一旦決定就不改了而反悔貪心允許你臨時反悔把之前某個決定撤銷掉。關(guān)鍵是刪掉哪一個這就是《學習軌跡》這道題真正的考點。2. 貪心策略推導與正確性證明2.1 掃描過程的核心維護量假設(shè)我們已經(jīng)把任務(wù)按截止時間升序排好了。掃描到第 i 個任務(wù)時維護兩個東西now當前已經(jīng)選中的所有任務(wù)按截止時間升序執(zhí)行最后一個任務(wù)完成所需的累計耗時一個數(shù)據(jù)結(jié)構(gòu)用來記錄當前已選任務(wù)中“耗時最大”的任務(wù)。每遇到一個新任務(wù) i先不管三七二十一把它加進計劃里然后讓now t_i。這時候如果now d_i說明新任務(wù)排在當前所有已選任務(wù)的最末尾也能在自己的截止時間前完成所以當前計劃合法繼續(xù)往下掃描。如果now d_i說明把任務(wù) i 加進來之后至少有一個任務(wù)的完成時間來不及了。這時候必須從當前已選任務(wù)中刪掉一個。因為任務(wù)數(shù)量目標是要最大化刪掉一個之后數(shù)量會回到原來的大小但我們剛剛嘗試過“加入一個”所以總體數(shù)量比原來多 0。我們要做的選擇就是刪掉哪一個讓剩下的集合對后續(xù)掃描最有利。2.2 超時之后為什么刪“耗時最大”的任務(wù)這是整個貪心算法最核心的判斷。不妨想一想刪掉一個任務(wù)之后會發(fā)生什么第一已選任務(wù)的數(shù)量減少 1 第二當前累計耗時now會減少被刪任務(wù)的耗時t。對于后面的任務(wù)來說它們關(guān)心什么只關(guān)心兩件事已經(jīng)完成了多少個任務(wù)以及當前累計耗時還有多少。累計耗時越小后面插入新任務(wù)的空間就越大。因此當必須刪一個任務(wù)時刪除耗時最大的那個任務(wù)可以讓now下降得最多留給后面的余量最大。但這樣會不會損失什么比如被刪掉的那個任務(wù)截止時間特別早后面有一個截止時間更晚的任務(wù)被保留了這會不會導致問題不會。因為截止時間更早的任務(wù)本身在加入時已經(jīng)驗證過合法了即使刪掉它也不會讓其他更早的任務(wù)變差而保留了截止時間更晚的任務(wù)只會在執(zhí)行順序上排在更后面對前面任務(wù)的完成時間沒有任何影響。反過來如果刪掉一個耗時較小但截止時間較晚的任務(wù)保留耗時最大的任務(wù)那么now下降得少而且耗時最大的任務(wù)還很占地方顯然更不利于后續(xù)。我們還可以從“支配”的角度來理解。當被迫要刪一個任務(wù)時我們面臨兩個候選方案方案 A 刪除耗時最大的任務(wù)方案 B 刪除另一個任務(wù)。方案 A 和方案 B 的任務(wù)數(shù)量相同但方案 A 的累計耗時更小。由于任務(wù)都可以按截止時間升序執(zhí)行累計耗時更小的方案里每個任務(wù)的完成時刻都不會比另一個方案更晚。也就是說方案 A 在可行性上支配了方案 B。所以刪除耗時最大的任務(wù)一定不會比刪除其他任務(wù)差。2.3 用“不變量”來總結(jié)正確性上面是直觀理解如果想讓自己更安心可以引入一個不變量來總結(jié)。假設(shè)掃描完前 i 個任務(wù)之后算法維護的集合 S 滿足在所有“僅從前 i 個任務(wù)中選出、并且能全部按時完成”的集合中S 的任務(wù)數(shù)最多在任務(wù)數(shù)最多的所有可行集合中S 的累計耗時最小。初始時 S 為空顯然滿足。加入新任務(wù) i 后如果直接合法那么任務(wù)數(shù)增加 1達到理論上界且總耗時是在原最優(yōu)集合基礎(chǔ)上加上 t_i可以論證它仍然是最小總耗時的集合。如果超時了說明想在前 i 個任務(wù)中實現(xiàn)比當前任務(wù)數(shù)多 1 的可行集合是不可能成功的于是我們回到原來的任務(wù)數(shù)此時為了保持“任務(wù)數(shù)最多且總耗時最小”必須從當前集合中去掉一個任務(wù)。去掉耗時最大的任務(wù)得到的集合在同樣任務(wù)數(shù)中總耗時最小不變量繼續(xù)成立。這個不變量成立意味著算法最終得到的一定是全局最優(yōu)任務(wù)數(shù)量最多而且在相同數(shù)量下累計耗時最小。這也是為什么它比 DP 更高效但不會比 DP 更差。2.4 幾個容易被忽略的細節(jié)細節(jié)一只檢查當前任務(wù)的截止時間夠不夠有人會擔心插入新任務(wù)后之前那些截止時間更早的任務(wù)會不會被影響不會。因為我們始終是按截止時間升序掃描的新插入的任務(wù)在最終執(zhí)行順序里一定排在所有已有任務(wù)之后。它不會改變前面任何一個任務(wù)的開始時間所以前面任務(wù)的完成時刻不會因為新任務(wù)的插入而變大。只要新任務(wù)自身在它的截止時間前完成整個集合就合法。細節(jié)二刪掉的可能就是剛加入的任務(wù)如果新任務(wù)的耗時特別大比如 ( t_i d_i )那么它一加入就會超時刪除耗時最大的任務(wù)時刪除的可能就是它自己。這相當于“嘗試加入后立刻放棄”是完全正常的。這個操作保證了算法不會強行選擇一個本身就不可能按時完成的任務(wù)。細節(jié)三全部任務(wù)都無法完成怎么辦極端情況下可能每個任務(wù)單獨做都會超時例如所有任務(wù)的 ( t_i d_i )。那么算法會不斷地加入、刪自己最后堆為空答案為 0。這種情況也要在實現(xiàn)上兼容輸出空軌跡即可。3. 代碼實現(xiàn)與手工模擬3.1 為什么選大根堆我們需要反復拿到當前已選任務(wù)中耗時最大的那個并且還可能隨時加入新任務(wù)。這個需求恰好是“優(yōu)先隊列”最擅長的。C 里可以用priority_queue默認就是大根堆堆頂是最大值。Python 里heapq是小根堆所以存耗時的時候取負數(shù)模擬大根堆。實現(xiàn)時還要注意一點題目最后要求輸出軌跡而堆里只能快速拿到最大元素沒有辦法按截止時間升序輸出所有元素。所以我們需要額外維護一個標記數(shù)組記錄哪些任務(wù)在最終集合中。最后再按照一開始排好的截止時間順序掃描一遍把標記為存活的任務(wù)輸出這個順序就是合法軌跡。3.2 C 參考實現(xiàn)#include bits/stdc.h using namespace std; struct Task { long long t; // 耗時 long long d; // 截止時間 int id; // 原始編號 }; int main() { int n; cin n; vectorTask 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_queuepairlong long, int pq; vectorchar 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; } } vectorint 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 常規(guī)版本。需要注意now和task.d都用long long因為耗時和截止時間都可能很大累加之后很容易超出int的范圍。3.3 Python 參考實現(xiàn)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 手工模擬一個完整樣例用下面這組數(shù)據(jù)來走一遍流程任務(wù)編號耗時 t截止時間 d134225316447528排序后順序就是 1、2、3、4、5。一開始now 0堆為空。處理任務(wù) 1加入now 33 4合法。堆里現(xiàn)在是{3}。處理任務(wù) 2加入now 55 5合法。堆里是{3, 2}。處理任務(wù) 3加入now 66 6合法。堆里是{3, 2, 1}。處理任務(wù) 4加入now 1010 7超時。此時堆頂是任務(wù) 4耗時 4所以把任務(wù) 4 刪掉now 10 - 4 6。堆里剩下{3, 2, 1}。處理任務(wù) 5加入now 88 8合法。堆里現(xiàn)在是{3, 2, 2, 1}。最終堆中有 4 個任務(wù)分別是任務(wù) 1、2、3、5。按截止時間順序輸出就是1 2 3 5。驗證一下任務(wù) 1完成于時刻 3截止 4合法任務(wù) 2完成于時刻 5截止 5合法任務(wù) 3完成于時刻 6截止 6合法任務(wù) 5完成于時刻 8截止 8合法。所以最優(yōu)軌跡就是 1 → 2 → 3 → 5答案 4。這里可以看到任務(wù) 4 雖然截止時間晚但耗時太長如果把它留下就必須刪掉任務(wù) 1最終總耗時反而更大。算法選擇刪除耗時最大的任務(wù)其實是在為后續(xù)任務(wù)留出更多空間。4. 常見問題與調(diào)試實錄4.1 排序的第二關(guān)鍵字要不要處理很多實現(xiàn)里只按截止時間升序排序相同截止時間的任務(wù)順序任意。這不會影響答案因為反悔貪心最終選出的集合和數(shù)量是一樣的。不過有一個小細節(jié)如果相同截止時間耗時大的任務(wù)放在前面可能會導致它加入后又立刻被刪掉多一次堆操作如果把耗時小的放在前面操作會少一點。但復雜度上都是 (O(n \log n))差別不大。我有一次在本地對拍時發(fā)現(xiàn)兩種排序得到的軌跡編號不一樣但答案數(shù)量和可行性完全一致后來想明白是因為存在多個最優(yōu)解。如果你希望輸出穩(wěn)定可以在排序時第二關(guān)鍵字按耗時升序或按編號升序這樣軌跡確定。4.2 為什么掃描時只判斷now d[i]就夠了這個問題我在學習的時候困惑了很久。因為當前已選任務(wù)里可能有截止時間比d[i]更早的任務(wù)如果now變大了會不會導致那些更早截止的任務(wù)超時答案是不會。因為在掃描過程中已選任務(wù)始終按截止時間升序排列新加入的任務(wù)一定排在末尾。更早的任務(wù)完成時刻不會因為后面插入新任務(wù)而改變。它們在自己被加入的那個時刻已經(jīng)驗證過合法了所以后續(xù)只需要檢查新加入的這個最晚截止任務(wù)即可。這個性質(zhì)是“按截止時間排序”帶來的紅利。如果一開始沒有排序這里的正確性就不成立了。4.3 堆空時能不能pop代碼里只有在now d[i]時才進入pop而這時剛剛push了當前任務(wù)所以堆一定不為空。不要在最外層寫一個“如果堆非空才 pop”之類的邏輯那樣反而可能掩蓋真正的問題。我見過有人這樣寫if (now d) { if (!pq.empty()) { ... } }這個寫法雖然不會 RE但會掩蓋一個邏輯漏洞如果堆是空的說明之前已經(jīng)出錯了不該繼續(xù)往下跑。正確的做法是在該刪除的時候堆一定非空直接pop就好。4.4 輸出軌跡時“堆里有什么”不等于“順序是什么”這是我第一次寫這個題時犯的錯。我直接把堆里剩下的任務(wù)編號pop出來當作軌跡結(jié)果順序完全亂。因為堆只保證能快速取出最大耗時元素并不維護截止時間順序。正確的輸出方式有兩種用alive標記數(shù)組最后再遍歷一次按截止時間排好的任務(wù)數(shù)組輸出存活任務(wù)的編號或者把所有存活任務(wù)的編號收集后重新按照這些任務(wù)原來的截止時間排序再輸出。第一種更簡單也更好調(diào)試。記住你維護“當前集合”用的是堆但輸出“軌跡”時要回到有序數(shù)組。4.5 用 DP 對拍驗證貪心為了確保貪心算法不是碰巧過樣例我寫了一個 (O(n^2)) 的 DP 用來對拍。DP 的狀態(tài)設(shè)計令dp[j]表示“處理完當前前綴完成 j 個任務(wù)所需的最小累計耗時”并且保證這 j 個任務(wù)按截止時間升序排列時都合法。初始dp[0] 0其余為無窮大。按截止時間升序遍歷每個任務(wù)對每個任務(wù)做反向更新vectorlong 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就是最優(yōu)任務(wù)數(shù)。這個 DP 的理解方式dp[j - 1]是完成前 j-1 個任務(wù)的最小耗時把當前任務(wù)作為第 j 個任務(wù)放到底只要dp[j - 1] t d就說明它能在截止時間前完成。反向更新保證每個任務(wù)最多被選一次。對拍時隨機生成小規(guī)模數(shù)據(jù)分別跑貪心和 DP比較答案數(shù)量、合法性、以及最終輸出軌跡是否確實不超時。跑了幾萬組之后我才敢確信這個貪心是對的。5. 擴展從“任務(wù)數(shù)量”到“加權(quán)收益”5.1 帶權(quán)任務(wù)調(diào)度的堆解法《學習軌跡》只要求最大化任務(wù)數(shù)量。如果把條件改成“每個任務(wù)還有一個收益 ( w_i )目標是總收益最大”那刪除策略就要變了。此時按截止時間排序的思路不變但超時后要刪除的是“收益最小”的任務(wù)而不是耗時最大的任務(wù)。具體做法是維護一個小根堆堆內(nèi)存當前已選任務(wù)的收益。每次嘗試加入新任務(wù)累加總耗時如果超時就從堆里彈出收益最小的任務(wù)并從總耗時里減去它的耗時。這樣可以保證在相同總耗時限制下保留的收益盡可能大。這個模型非常經(jīng)典很多任務(wù)調(diào)度題都是它的變體。5.2 “學習總時長最長”與“數(shù)量最多”的差別如果題目問的不是“最多能完成幾個任務(wù)”而是“在合法前提下最多能累計學習多長時間”那又是另一種趣味。這時候每個任務(wù)的收益就是它的耗時本身。用帶權(quán)調(diào)度的方法超時時刪除收益最小的任務(wù)也就是刪除耗時最短的任務(wù)。你會發(fā)現(xiàn)這個策略和“數(shù)量最多”恰好相反一個努力留下耗時短的任務(wù)一個努力留下耗時長但價值高的任務(wù)。同樣是反悔貪心不同的優(yōu)化目標導致不同的刪除優(yōu)先級。這個對比非常值得自己推一遍能加深對“反悔貪心核心在于維護不變量”的理解。5.3 更進一步的學習建議如果你把《學習軌跡》吃透了可以繼續(xù)看這些方向帶截止時間、耗時和收益的通用調(diào)度問題核心是排序 堆多臺機器并行學習的變體需要用多個堆或者可撤銷堆來維護依賴關(guān)系下的學習路徑規(guī)劃那就要結(jié)合拓撲排序、樹形 DP 甚至反悔貪心一起考慮。算法競賽里很多題都是這樣表面上是“軌跡”“路徑”“規(guī)劃”剝開之后底層是一個經(jīng)典模型。學會從題目包裝里找到核心矛盾比背某個特定解法重要得多。6. 一點個人經(jīng)驗這種“排序 反悔刪除”的貪心題我踩過最多次的坑不是想不到堆而是沒有想清楚“刪除哪個”背后的優(yōu)化目標。只看任務(wù)數(shù)量時刪除耗時最大看總收益時刪除收益最小。不要死記一定要從“刪除一個任務(wù)后對后續(xù)狀態(tài)有什么影響”出發(fā)去推導。如果你也正在學貪心我建議拿到一道調(diào)度題先別急著寫代碼先回答三個問題第一固定選擇集合后最優(yōu)執(zhí)行順序是什么第二當前維護的狀態(tài)里哪個量決定了后面的可行性第三被迫放棄一個任務(wù)時放棄標準應該是什么這三個問題想明白代碼只是最后一步。最后分享一個調(diào)試小技巧寫對拍的時候不要只比較答案數(shù)量還要把貪心輸出的軌跡真正模擬執(zhí)行一遍逐個檢查每個任務(wù)的完成時間是否小于等于截止時間。很多反悔貪心實現(xiàn)看起來答案對但軌跡是錯的問題往往出在輸出順序上。用alive標記數(shù)組從有序數(shù)組里收集答案是最穩(wěn)妥的方式。