---
# System prepended metadata

title: 2462. Total Cost to Hire K Workers
tags: [Heap / Priority Queue]

---

思考:
1.題目條件式是從第一批和最後一批候選人開始搜尋->頭尾建立min-heap
2.維護頭尾的min-heap的大小在一批候選人的數量內，並且node不能重複，因為每次面試人選不重複人
3.如果cost相同優先選擇第一批
```c++=
class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        //用i和j是為了兩顆min-heap不會重複node，因為面試人選不會重複
        int i = 0; // 起始
        int j = costs.size() - 1; // 結束
        priority_queue<int, vector<int>, greater<int>> minHeap1; // minHeap1，第一次面試人選
        priority_queue<int, vector<int>, greater<int>> minHeap2; // minHeap2，第二次面試人選
        //因為回傳的是long long
        long long ans = 0; // 答案
        //找到k個人
        while(k){
            // 每一個min-heap的node不超過每一次面試的人數
            // 用i和j去確保兩棵樹不會有重複的node
            while(minHeap1.size() < candidates && i <= j){
                minHeap1.push(costs[i++]);
            }
            while(minHeap2.size() < candidates && i <= j){
                minHeap2.push(costs[j--]);
            }
            
            // int minV1,minV2;
            //檢查樹有沒有點，避免錯誤，可以寫成三元判斷式
            // if(minHeap1.size() > 0){
            //     minV1 = minHeap1.top();
            // }else{
            //     minV1 = INT_MAX;
            // }
            // if(minHeap2.size() > 0){
            //     minV2 = minHeap2.top();
            // }else{
            //     minV2 = INT_MAX;
            // }
            int minV1 = minHeap1.size() > 0 ? minHeap1.top() : INT_MAX;
            int minV2 = minHeap2.size() > 0 ? minHeap2.top() : INT_MAX;
            //判斷大小
            //costs相同則優先選擇第一批面試的人
            if(minV1 <= minV2){
                ans += minV1; 
                minHeap1.pop(); 
            }
            else{
                ans += minV2;
                minHeap2.pop();
            }
            k--;
        }
        return ans; 
    }
};
``` 

```c++=
class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        //從第一次面試和最後一次面試人選開始搜尋最小成本，k次
        long long ans;
        priority_queue <int, vector<int>, greater<int>> h1;
        priority_queue <int, vector<int>, greater<int>> h2;
        int i = 0;
        int j = costs.size()-1;
        while(k){
            //建立兩顆min-heap
            //維護兩顆tree的size，考慮每一批面試人員不重複
            while(h1.size() < candidates && i <= j ){
                h1.push(costs[i]);
                i++;
            }
            while(h2.size() < candidates && i <= j){
                h2.push(costs[j]);
                j--;
            }
            
            int temp1 = h1.size() > 0 ? h1.top() : INT_MAX;
            int temp2 = h2.size() > 0 ? h2.top() : INT_MAX;
            
            if(temp1 <= temp2){
                ans += temp1;
                h1.pop();
            }else{
                ans += temp2;
                h2.pop();
            }
            k--;
        }
        return ans;
    }
};

```