### 2462. Total Cost to Hire K Workers#

You are given an integer array `costs`

where `costs[i]`

is the cost of hiring the `i-th`

worker.

You are also given two integers `k`

and `candidates`

. We want to hire exactly `k`

workers according to the following rules:

- There are
`k`

rounds of hiring, and in each round, exactly one worker is hired. - In each round of hiring, we select the worker with the minimum cost from the first
`candidates`

workers and the last`candidates`

workers. If there are multiple workers with the same minimum cost and different indices, we select the worker with the smaller index.- For example, if
`costs = [3,2,7,7,1,2]`

and`candidates = 2`

, in the first round of hiring, we select the worker at index`4`

because their cost is the minimum. - In the second round of hiring, we select the worker at index
`1`

because their cost is the same as the worker at index`4`

and their index is smaller. Note that after each round of hiring, the indices of the remaining workers may change.

- For example, if
- If there are fewer than
`candidates`

workers remaining, we hire the worker with the minimum cost from the remaining workers. If there are multiple workers with the same minimum cost and different indices, we select the worker with the smaller index. - Each worker can only be selected once.

Return the total cost of hiring exactly `k`

workers.

**Example 1:**

```
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We will hire 3 workers in total. The total cost starts at 0.
- In the first round, we select the worker from [17,12,10,2,7,2,11,20,8]. The minimum cost is 2, and there are two workers with that cost. We select the worker with the smaller index, which is the worker at index 3. The total cost is 0 + 2 = 2.
- In the second round, we select the worker from [17,12,10,7,2,11,20,8]. The minimum cost is 2, and the index is 4. The total cost is 2 + 2 = 4.
- In the third round, we select the worker from [17,12,10,7,11,20,8]. The minimum cost is 7, and the index is 3. The total cost is 4 + 7 = 11. Note that the worker at index 3 is both at the front and back of the remaining 4 workers.
The total cost is 11.
```

**Example 2:**

```
Input: costs = [1,2,4,1], k = 3, candidates = 3
Output: 4
Explanation: We will hire 3 workers in total. The total cost starts at 0.
- In the first round, we select the worker from [1,2,4,1]. The minimum cost is 1, and there are two workers with that cost. We select the worker with the smaller index, which is the worker at index 0. The total cost is 0 + 1 = 1. Note that the workers at index 1 and 2 are both at the front and back of the remaining 3 workers.
- In the second round, we select the worker from [2,4,1]. The minimum cost is 1, and the index is 2. The total cost is 1 + 1 = 2.
- In the third round, there are fewer than 3 workers remaining, so we select the worker with the minimum cost from the remaining workers, which is 2. The total cost is 2 + 2 = 4.
The total cost is 4.
```

**Note:**

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

### Priority Queue#

```
class Solution {
public:
long long totalCost(vector<int>& costs, int k, int candidates) {
int n = costs.size();
// If the sum of the first candidates and the last candidates in the costs array is greater than the size of the costs array,
// we only need the costs of the first k smallest workers.
if (candidates * 2 >= n) {
sort(costs.begin(), costs.end());
return accumulate(costs.begin(), costs.begin() + k, 0LL);
}
using PII = pair<int, int>;
auto cmp = [&](const PII &p1, const PII &p2) {
return p1.first == p2.first ?
p1.second > p2.second : p1.first > p2.first;
};
priority_queue<PII, vector<PII>, decltype(cmp)> heap(cmp);
// priority_queue<PII, vector<PII>, greater<PII>> heap;
// Two intervals, the first candidates and the last candidates
// left1, ..., right1, ..., left2, ..., right2
int left1 = 0, right1 = candidates - 1;
int left2 = n - candidates, right2 = n - 1;
for (int i = left1; i <= right1; ++i) {
heap.push({costs[i], i});
}
for (int i = left2; i <= right2; ++i) {
heap.push({costs[i], i});
}
long long res = 0;
while (k--) {
auto t = heap.top();
heap.pop();
res += t.first;
// If the two intervals overlap
if (right1 + 1 == left2) {
continue;
}
if (t.second <= right1) {
++right1;
heap.push({costs[right1], right1});
} else {
--left2;
heap.push({costs[left2], left2});
}
}
return res;
}
};
```