題幹與適用場景
給定工作 (start, end, reward)，選擇兩兩相容的工作以最大化收益。若一個工作在時間 t 結束，另一個在 t 開始，兩者可以同時選。例：(1,3,50)、(3,5,40)、(2,6,100) 的最佳選擇是前兩個工作，總收益 90。題目屬於 coding，核心能力是區間排序、前驅查詢與動態規劃，不因實作語言歸入前端。
公開演算法題資料把 weighted interval/job scheduling 作為動態規劃與區間模式練習；公開面經記錄也出現 interval scheduling 變體。應描述可核驗的演算法要求，不宣稱無法核驗的面試頻率。
面試官考察點
- 能否先依結束時間排序，讓「最後選的工作」成為有序決策。
- 能否定義
p(i)：在工作i開始前結束的最後一個相容工作。 - 能否寫出「跳過目前工作」與「選擇目前工作」的完整轉移，而非貪心只選目前收益最高者。
- 能否用二分搜尋把前驅查詢降到
O(log n)，並說明如何回復所選工作。 - 能否處理
end == start、相同結束時間、空陣列與收益為零。
回答前需要澄清的問題
- 結束時間等於開始時間是否相容？本文按相容處理，前驅條件為
end <= start。 - 收益是否可能為負數？若可能，應明確允許一個工作都不選，基線收益為
0。 - 是否只回傳最大收益？本文同時回復工作集合；只要收益時可省略回溯陣列。
- 時間是否為整數？排序只需要可比較值，二分搜尋不要求連續整數。
- 是否允許同一工作重複？預設每個輸入工作最多選一次。
- 輸入是否可能
start > end？標準約束應拒絕或先規範化，不能讓轉移默默吞掉錯誤資料。 - 相同區間如何處理？採穩定 tie-break，收益相同即可。
30 秒回答框架
「我先依 end 升冪排序，令 dp[i] 表示前 i 個工作的最大收益。對第 i 個工作，用二分搜尋找到最後一個滿足 end <= start[i] 的工作數量 p。轉移是 dp[i] = max(dp[i-1], reward[i] + dp[p])：前者跳過目前工作，後者選擇目前工作並接上相容前綴。保存選擇標記後從尾端回溯工作。排序是 O(n log n)，每次二分也是 O(log n)，總時間 O(n log n)，空間 O(n)。」
分步驟深入解答
第一步：說明貪心為何不足。
依最早結束時間的經典貪心只適合每個工作收益相同。收益不同時，短工作可能收益很低，不能只看結束時間或單一收益做局部決策。
第二步：定義有序狀態。
排序後令 dp[i] 表示前 i 個工作（索引 0..i-1）的最佳收益，dp[0] = 0。不選工作 i-1 時直接落到 dp[i-1]。
第三步：計算前驅。
對工作 i-1，找最大的 j < i-1，滿足 end[j] <= start[i-1]。用結束時間二分搜尋，回傳相容工作數量 p；選擇該工作的收益是 reward[i-1] + dp[p]。
第四步：寫出轉移與回復。
dp[0] = 0
for i = 1..n:
skip = dp[i - 1]
take = reward[i - 1] + dp[p(i - 1)]
dp[i] = max(skip, take)
chose[i] = take > skip從 i = n 倒推：若 chose[i] 為真，記錄工作 i-1 並跳到 p(i-1)；否則跳到 i-1。收益相等時固定一種 tie-break，兩者都正確。
第五步：正確性證明。
考慮前 i 個工作的任一最佳解。它要嘛不含工作 i-1，收益至多為 dp[i-1]；要嘛含工作 i-1，其餘工作必須來自前 p(i-1) 個工作，收益至多為 reward[i-1] + dp[p(i-1)]。兩者最大值就是轉移式。以 dp[0]=0 為基底歸納，所有狀態皆最佳。
第六步：實作邊界。
二分搜尋必須使用 <=，否則會錯誤排除剛好首尾相接的工作。收益為零時允許空集合；收益可能為負時，dp 仍從零開始。回溯結果要反轉，因為恢復方向由後往前。
第七步：複雜度。
排序 O(n log n)；每個工作一次二分 O(log n)，總時間 O(n log n)。dp、前驅陣列與選擇標記使用 O(n) 空間；輸出的工作列表另行說明大小。
第八步：替代方案。
若結束時間是小範圍整數，可用座標壓縮或按時間掃描；若每個工作收益相同，可退化為最早結束時間貪心。若增加最多選 k 個工作或多資源限制，狀態必須增加維度。
高品質示範回答
「我會先依結束時間排序，令 dp[i] 表示前 i 個工作的最大收益。對每個工作 i，二分搜尋最後一個 end <= start[i] 的前驅 p(i)。不選它是 dp[i-1]；選它是 reward[i] + dp[p(i)]，因此取兩者最大值。回溯時根據兩項大小恢復工作集合。正確性來自任一最佳解都可依是否包含目前工作分成兩類，包含時剩餘工作只能來自相容前綴。排序和二分使總時間 O(n log n)，陣列空間 O(n)。我會測試首尾相接、相同結束時間、負收益、全重疊和空輸入。」
常見錯誤
- 按收益最高的工作貪心 → 高收益工作可能擋住兩個總和更高的工作 → 使用選擇/跳過轉移。
- 把相等結束時間判成衝突 → 合法相鄰工作被丟掉 → 使用
end <= start。 - 只依開始時間排序 →
dp[i-1]不再代表穩定前綴 → 依結束時間排序。 - 前驅線性掃描 → 總複雜度退化
O(n²)→ 對結束時間做二分搜尋。 dp從第一個收益初始化 → 全負收益時無法選空集合 → 設定dp[0] = 0。- 回溯後忘記反轉 → 工作順序倒置 → 收集後反轉。
- 相等收益沒有固定 tie-break → 輸出不穩定 → 固定規則，只保證收益與相容性。
- 宣稱可直接支援資源限制 → 一維狀態無法描述額外條件 → 增加維度或重新建模。
追問及應對
追問一：為什麼相等時仍可選舊工作？
在本題的回復規則中，選擇新工作或舊工作只要收益相等都正確；若要保留最早出現的最大值，前驅與 tie-break 必須明確固定。這與單調佇列題的淘汰規則不同，不能混用。
追問二：如何只用 O(n) 時間？
若時間座標是小範圍整數，可按結束時間線性掃描並直接尋找前驅；一般比較模型下排序本身需要 O(n log n)，不能無條件宣稱線性。
追問三：如何回復具體工作？
保存 chose[i] 或父指標。從 i=n 開始，選目前工作就加入結果並跳到 p(i)，否則減一，最後反轉。
追問四：若最多只能選 k 個工作？
增加選取數量維度，例如 dp[i][c] 表示前 i 個工作選 c 個的最大收益；時間與空間都會增加。
追問五：若收益會隨相鄰工作改變？
獨立收益假設失效。需把相鄰關係納入狀態，或把收益變化建模成轉移成本，不能直接沿用原轉移。
追問六：所有工作結束時間都相同怎麼辦？
維持穩定排序即可。前驅通常相同，轉移仍會逐個比較；完全相同區間只保留收益較佳的選擇。
追問七：什麼時候貪心才正確？
當所有工作收益相同、目標是選最多工作時，最早結束時間貪心有交換論證。收益不同後論證失效，應改用加權動態規劃。