題幹與適用場景
請實作單機 Scheduler，支援 schedule(taskId, runAt, priority, fn)、cancel(taskId) 與 next()。選擇規則是先取最早 runAt，相同時取較高 priority，仍相同時依提交序號；同一 taskId 只能有一個有效版本。取消後不得執行，沒有到期任務時 next() 回傳等待資訊或空值。請說明惰性刪除、並行 worker、時鐘與關閉競態。
公開面試資料把任務調度器列為結合優先隊列、執行緒池、取消與失敗處理的綜合題。它比單獨實作優先隊列多出生命週期與並行契約，能檢驗資料結構不變量是否真正落到可執行介面。
面試官考察重點
- 能否定義
pending、running、cancelled、completed狀態並禁止非法回退。 - 能否用
(runAt, -priority, sequence)建立確定排序，避免任務物件不可比較。 - 能否以版本號或惰性刪除處理重複排程與取消，讓舊堆項不會洩漏執行。
- 能否區分取消排隊任務與中止已執行函式。
- 能否證明 worker 數量、關閉順序與時鐘選擇不會破壞邊界。
回答前需要釐清的問題
runAt使用單調時鐘的相對時間，還是可校準的牆上時間？本題用單調時鐘計算等待。fn是否接收取消訊號？預設接收AbortSignal，但只能合作式停止。- 重複
taskId是更新還是報錯？本題更新舊版本並使舊堆項失效。 cancel是否保證執行中的函式立即停止？不保證，只阻止尚未開始的執行並發出訊號。close是否等待已執行任務？預設拒絕新任務並等待 worker 收尾。
30 秒回答框架
我會用最小堆保存 (runAt, -priority, sequence, taskId, version)，再以字典保存每個任務 ID 的目前版本。更新或取消只改變字典狀態並讓舊堆項失效；next() 彈出堆頂時反覆檢查版本和狀態，只有目前且到期的任務才能進入 running。調度執行緒以單調時鐘計算距離堆頂的等待時間，worker 以固定並行上限執行函式。排隊取消是強保證，執行中取消是合作式語意；關閉先拒絕新任務，再喚醒調度執行緒並等待收尾。
分步驟深入解答
第一步：固定排序鍵與狀態不變量
堆元素排序鍵是 (runAt, -priority, sequence)；sequence 單調遞增，讓相同時間和優先級仍有確定順序。字典 current[taskId] 只保存最新版本。舊版本可以暫留堆中，但永遠不能從 pending 轉為 running。
第二步：實作 schedule 的更新語意
每次 schedule 產生新版本並寫入字典，再壓入新堆項。已有舊版本時不必在線性陣列刪除，只要讓字典指向新版本，彈出時比較版本即可。插入是 O(log n)，重複 ID 不會造成兩次有效執行。
schedule(id, runAt, priority, fn):
version = nextVersion(id)
current[id] = {version, state: pending, fn, runAt, priority}
heappush(heap, (runAt, -priority, nextSequence(), id, version))第三步：實作 cancel 與堆頂清理
取消時讀取字典中的目前任務；仍是 pending 就標記 cancelled 並喚醒等待者。next() 彈出堆頂後檢查字典是否仍指向同一版本，以及狀態是否為 pending。失效項、已取消項與舊版本直接丟棄。惰性刪除避免 O(n) 掃描，但要統計失效比例並在達到門檻時重建堆。
第四步：處理到期與 worker 上限
調度執行緒不能把未到期任務立即交給 worker。它讀取堆頂 runAt，用單調時鐘計算等待；到期後原子地把任務由 pending 改為 running，再送入固定大小的 worker 佇列。並行上限由 worker 數或 semaphore 保證。
第五步：區分取消與函式中止
排隊任務在狀態轉換前被取消時不會呼叫 fn。進入 running 的任務只能收到 AbortSignal；函式必須主動檢查訊號或傳給可取消 I/O。調度器記錄 cancelRequested，不把尚未確認退出的函式誤報為完成。
第六步：設計 close 的競態順序
close 先將調度器設為 closing，拒絕新的 schedule，再取消計時器並喚醒調度執行緒。調度執行緒停止領取新任務，worker 繼續處理已領取任務；所有 worker 結束後才變成 closed。若要立即丟棄排隊任務，需明確標記字典狀態，不能只清空堆。
第七步：證明複雜度與空間邊界
正常 schedule 為 O(log n)，cancel 為 O(1) 標記，next 的堆操作為 O(log n)。每個失效堆項最多彈出一次，清理成本可攤銷到產生它的更新或取消。長期只更新不消費會增加空間；堆長度超過有效任務固定倍數時，從字典重建。
第八步：測試關鍵交錯
測試相同時間與優先級的穩定順序、重複 ID 更新後舊版本不執行、取消恰好發生在領取前後、早期新任務打斷等待、worker 達到上限、函式拋錯、關閉期間提交以及單調時鐘跳變。用排序列表模型對拍 next()，並記錄最大活動 worker 數。
高品質示範回答
我會分開維護狀態與堆：字典保存每個 taskId 的最新版本，最小堆保存 (runAt, -priority, sequence, taskId, version)。更新採用新版本覆蓋，取消採用狀態標記；兩者都不直接修改堆陣列。調度執行緒只在任務到期後原子領取，放入固定大小的 worker 佇列。領取前的版本檢查保證取消與舊版本不會執行，執行後的取消則透過 AbortSignal 合作式處理。關閉先拒絕新提交，再停止領取、喚醒等待者並等待已執行任務收尾。
常見錯誤
- 只依優先級排序，忽略未到期的
runAt。 - 更新時直接修改堆內元素，破壞堆不變量。
- 取消只刪字典，彈出舊堆項時仍呼叫函式。
- 把
cancel()成功等同於執行中函式已停止。 - 用牆上時間計算等待，校時後出現負等待或飢餓。
close()只清空佇列，留下調度執行緒、計時器或 worker。- 沒有限制 worker 數，壓力上來後變成無界並行啟動器。
追問及應對
高優先級任務持續到來，如何避免低優先級飢餓？
先說明題目預設嚴格優先級，低優先級可能長時間等待。需要公平性時，可讓等待時間逐步提升有效優先級，或使用分層配額的加權公平佇列；這會改變排序鍵與延遲證明。
如何支援重複任務而不重疊執行？
在狀態加入 running 鎖或 generation。下一次觸發若仍在 running，依契約選擇跳過、合併一次待執行標記或排入新版本；不能無條件再次提交。
程序崩潰後怎樣恢復任務？
記憶體堆只能保證程序存活期間的調度。持久化版本、狀態與下次執行時間，重啟時重建堆；領取需條件更新或租約。恢復通常只能提供至少一次執行，因此函式要具備冪等性。
如何擴展到多節點？
把堆替換成帶時間索引的持久佇列，以租約或條件寫入確保單一 owner。節點故障後讓租約過期再重試；取消與更新攜帶版本號，消費者拒絕過期版本。跨節點時鐘需使用儲存端時間或明確容忍窗口。