2462. The total cost of employing K workers

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.
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;
    }
};

2462. The total cost of employing K workers

2462. Total Cost to Hire K Workers#

Priority Queue#

2462. Total Cost to Hire K Workers #