2462. Total Cost to Hire K Workers

📘 題目敘述

給你一個 0-indexed 的整數陣列 costs，其中 costs[i] 是雇用第 i 位工人的成本。

另外給你兩個整數 k 和 candidates。我們想要依照以下規則雇用剛好 k 位工人：

你會進行 k 次 session，每次 session 會雇用剛好一位工人。
在每一次雇用 session 中，從「前 candidates 位工人」或「後 candidates 位工人」中選擇成本最低的工人。若成本相同，選擇索引較小的那位。
例如，若 costs = [3,2,7,7,1,2] 且 candidates = 2，那在第一次雇用 session 中，我們會選第 4 位工人，因為他是最低成本 [3,2,7,7,1,2]。
在第二次雇用 session 中，我們會選第 1 位工人，因為他與第 4 位工人同樣是最低成本，但索引較小 [3,2,7,7,2]。請注意，在這個過程中索引可能會改變。

如果剩下的工人數量少於 candidates，就從剩下的工人中選擇成本最低者。若成本相同，選擇索引較小的那位。
同一位工人只能被選一次。

回傳雇用剛好 k 位工人的總成本。

條件限制

• 1 <= costs.length <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= k, candidates <= costs.length

🧠 解題思路

題目每一輪只能從「左邊前 candidates」或「右邊後 candidates」這兩個區域挑最小成本，因此我用兩個 min-heap 來分別維護左右兩側目前可選的人：

• 左邊可選集合丟進 lq
• 右邊可選集合丟進 rq

然後用兩個指標 l、r 控制「下一個要補進 heap 的位置」：

• l 代表目前左邊已經放進 lq 的最右端位置（下一個要補的是 l+1）
• r 代表目前右邊下一個可以放進 rq 的位置（每次補完就 r--）

每次雇用（總共 k 次）就比較 lq.top() 與 rq.top()，挑比較小的成本；若同成本，我的寫法會優先選左邊。選完之後，再從同一側補一個新工人進來，直到左右指標交錯為止。

所有變數

• lq：左側候選人的 min-heap，top() 永遠是目前左側可選的最低成本
• rq：右側候選人的 min-heap，top() 永遠是目前右側可選的最低成本
• l：左側目前已經放入 lq 的最右端索引（左側已放入的範圍是 0..l）
• r：右側下一個準備放入 rq 的索引（每次放入後就 r--，用來逐步往左補）
• ans：目前累積的總成本

🪜 主要流程步驟

1. 先把左邊前 candidates 個人丟進 lq

l 從 -1 開始往右推，推到 candidates-1，把 costs[0..candidates-1] 依序丟進 lq。

2. 再把右邊後 candidates 個人丟進 rq（注意不要跟左邊重疊）

r 從最右邊開始往左放，把右側的候選人丟進 rq。
同時用 l < r 避免左右候選區域重疊（例如陣列很短、或 candidates 很大時）。

3. 做 k 次雇用：每次從 lq 或 rq 取較小的成本

每一輪比較：

• 如果 rq 是空的，就只能從 lq 取
• 否則如果 lq.top() <= rq.top()，就從 lq 取
• 否則從 rq 取

取到的值加進 ans。

4. 從被取走的那一側補一個新候選人進 heap

如果是從 lq 取走，就嘗試把 l+1 的人補進 lq。
如果是從 rq 取走，就嘗試把 r 的人補進 rq，然後 r--。
補之前都用 l < r 檢查是否還有「尚未進入任何 heap」的候選人可以補。

5. k 次結束後回傳 ans

代表已經雇用完剛好 k 位工人。

⏱️ 複雜度

• 時間複雜度：O((candidates + k) log candidates)（兩個 heap 的大小都不會超過 candidates，每次 push/pop 都是 log candidates）
• 空間複雜度：O(candidates)（兩個 heap）

💻 程式碼實作

class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        priority_queue<int, vector<int>, greater<int>> lq;
        priority_queue<int, vector<int>, greater<int>> rq;
        int l = -1, r = costs.size() - 1; // l有包含，r沒有
        while (l < candidates - 1) {
            l++;
            lq.push(costs[l]);
        }
        while (r > costs.size() - candidates - 1 && l < r) {
            rq.push(costs[r]);
            r--;
        }
        long long ans = 0;
        while (k > 0) {
            if (rq.empty() || (!lq.empty() && lq.top() <= rq.top())) {
                ans += lq.top();
                lq.pop();
                if (l < r) {
                    l++;
                    lq.push(costs[l]);
                }
            } else {
                ans += rq.top();
                rq.pop();
                if (l < r) {
                    rq.push(costs[r]);
                    r--;
                }
            }
            k--;
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/problems/total-cost-to-hire-k-workers/