2462. Total Cost to Hire K Workers
解題說明
Total Cost to Hire K Workers
題目描述:給定一個整數陣列 costs,其中 costs[i] 代表雇用第 i 個工人的費用。每一輪雇用中,你可以從 前 candidates 個或後 candidates 個尚未被雇用的工人中,選出費用最低的一位(若費用相同則選 index 較小者)。共進行 k 輪,求總雇用費用的最小值。
解題思路:
使用雙 min-heap 搭配雙指針模擬整個雇用過程:
- 維護兩個最小堆:
leftHeap(管理左側候選人)和rightHeap(管理右側候選人),各自預先放入candidates個工人。 - 用兩個指針
left和right分別記錄左側下一個可補充的位置和右側下一個可補充的位置,確保兩側不重疊。 - 每輪比較兩個 heap 的堆頂元素,取費用較小者(若相同取 index 較小者)加入總費用,並從對應的 heap 中移除該工人。
- 移除後,若左右指針尚未交叉,則從對應側補充一名新工人進入 heap。
- 重複
k次,累加費用即為答案。
雙 heap 確保每輪都能在 O(log n) 時間內取得兩側的最小值,整體貪心地最小化總費用。
C++ 解法
複雜度分析
時間複雜度:O((k + candidates) × log(candidates)) — 預填兩個 heap 各需 O(candidates × log(candidates));每輪 heap 操作(pop + push)為 O(log(candidates)),共進行 k 輪,因此總時間為 O((k + candidates) × log(candidates))。
空間複雜度:O(candidates) — 兩個 min-heap 各最多持有 candidates 個元素,額外空間為 O(candidates)。
虛擬碼
1. Initialize two min-heaps: leftHeap and rightHeap
2. Set pointers: left = 0, right = n - 1
3. Pre-fill leftHeap with the first `candidates` workers:
a. Push (costs[left], left) into leftHeap, increment left
b. Stop when candidates filled or left > right
4. Pre-fill rightHeap with the last `candidates` workers:
a. Push (costs[right], right) into rightHeap, decrement right
b. Stop when candidates filled or left > right
5. Repeat k times:
a. Compare tops of leftHeap and rightHeap
b. Choose the side with the smaller cost (tie-break: smaller index)
c. Add the chosen cost to total
d. Pop the chosen worker from its heap
e. If left <= right, replenish the chosen side:
- If picked from left: push (costs[left], left), left++
- If picked from right: push (costs[right], right), right--
6. Return total其他解法
排序暴力法 O(k × n):每輪線性掃描前 candidates 和後 candidates 個工人,找出最小費用者並標記為已雇用。實作簡單,但 k 和 n 較大時會 TLE,不適合本題的資料規模。
單一 min-heap + 標記法 O((k + candidates) × log(n)):將所有候選人(前 candidates + 後 candidates)加入同一個 heap,並以 index 判斷屬於左側或右側;雇用後補充對應側的下一位工人。邏輯與雙 heap 等效,但使用單一 heap 需在 push 時額外區分左右側,code 略複雜。兩種 heap 方法的複雜度實質相同,雙 heap 版本結構更清晰。
延伸思考
- 如果每輪可以從前
candidates個或後candidates個工人中同時選出多位,且總數固定為k,演算法需要如何調整? - 若工人的費用會隨輪次動態變化(例如每輪費用乘以某個係數),雙 heap 的策略是否仍然適用?應如何修改?
- 如果題目要求雇用費用的最大值最小化(minimax 問題),而非最小化總費用,應改用什麼資料結構或演算法?