1235. Maximum Profit in Job Scheduling

Maximum Profit in Job Scheduling

題目描述： 有 n 個工作，第 i 個工作在時間 [startTime[i], endTime[i]) 執行並獲得 profit[i] 的利潤。選擇若干工作（時間不重疊，結束時間等於下一個開始時間視為不衝突），使總利潤最大。

解題思路：DP + 二分搜尋：

將工作依結束時間排序，定義 dp[i] 為考慮前 i 個工作（0 表示不選任何工作）能獲得的最大利潤。

對第 i 個工作（1-indexed），有兩種選擇：

1. 不選：dp[i] = dp[i-1]
2. 選：需找到最後一個結束時間 ≤ 當前工作開始時間的工作索引 k，dp[i] = dp[k] + profit[i-1]
   • 在已排序的結束時間陣列中用二分搜尋求 k，效率為 O(log n)。

dp[i] = max(dp[i-1], dp[k] + profit[i-1])

實作細節：

• 將三個陣列合併後依 endTime 排序。
• 同步維護一個 endTimes 陣列（記錄前 i 個工作的結束時間），供二分搜尋使用。
• 二分搜尋目標：找最大的 k 使得 endTimes[k-1] <= startTime[i-1]，即 upper_bound 之前。

時間複雜度：O(n log n) — 排序 O(n log n)；每個工作做一次二分搜尋 O(log n)，共 O(n log n)。整體由排序主導。

空間複雜度：O(n) — jobs 陣列、dp 陣列、ends 陣列各佔 O(n) 空間。

map 代替 dp 陣列（程式碼更精簡）：用 map<int,int> 以結束時間為 key 儲存最大利潤，每次利用 upper_bound 查詢，最後取最大值。邏輯等價，但常數稍大。

記憶化遞迴（Top-Down DP）：先按結束時間排序，定義 solve(i) = 從第 i 個工作開始能獲得的最大利潤；對每個工作選擇選或不選，用二分搜尋跳到下一個不衝突的工作。時空複雜度相同，遞迴版本在面試中更直觀但需額外的遞迴棧空間。

線段樹 / BIT：若工作時間為離散整數且範圍不大，可以用線段樹做區間最大值查詢，避免排序依賴，但實作較複雜，不適合作為首選解法。

1. 若允許兩個工作重疊（但最多同時執行 k 個），問題如何演變？這會讓 DP 的狀態設計如何改變？
2. 本題排序後用 upper_bound 找「最後一個結束時間 ≤ start」等同於 lower_bound(start+1) - 1。請解釋這兩種寫法在語義上是否完全等價，有無邊界條件的差異？
3. 本題與 LeetCode 435（Non-overlapping Intervals，貪心求最少移除區間數）都處理區間排程問題，但思路完全不同（貪心 vs. DP）。你如何判斷一個區間問題應該用貪心還是 DP 解決？