diff options
Diffstat (limited to 'other/cost_hire_k_worker.cpp')
-rw-r--r-- | other/cost_hire_k_worker.cpp | 48 |
1 files changed, 0 insertions, 48 deletions
diff --git a/other/cost_hire_k_worker.cpp b/other/cost_hire_k_worker.cpp deleted file mode 100644 index 5bb0860..0000000 --- a/other/cost_hire_k_worker.cpp +++ /dev/null @@ -1,48 +0,0 @@ -// 2462. Total Cost to Hire K Workers -#include "leetcode.h" - -/* - * given a 0-indexed integer array 'costs' where 'costs[i]' is the cost of - * hiring the i'th worker. you are also given two integers 'k, candidates'. we - * want to hire exactly 'k' workders according to the following rules: - * - you will run 'k' sessions and hire exactly one worker in each session - * - in each hiring session, choose the worker with the lowest cost from either - * the first 'candidates' workers or the last 'candidates' workers. break the - * tie by the smallest index. - * - if there are fewer than candidates workers remaining, choose the workder - * with the lowest cost among them. break the tie by the smallest index. - * - a worker can only be chosen once - * return the total cost to hire eactly 'k' workers. - */ - -class Solution { -public: - long long totalCost(vector<int> &costs, int k, int candidates) { - int i = 0, j = costs.size() - 1; - priority_queue<int, vector<int>, greater<int>> pq1, pq2; - long long ans; - while (k--) { - while (pq1.size() < candidates && i <= j) - pq1.push(costs[i++]); - while (pq2.size() < candidates && i <= j) - pq2.push(costs[j--]); - int t1 = pq1.size() > 0 ? pq1.top() : INT_MAX; - int t2 = pq2.size() > 0 ? pq2.top() : INT_MAX; - if (t1 <= t2) { - ans += t1; - pq1.pop(); - } else { - ans += t2; - pq2.pop(); - } - } - return ans; - } -}; - -int main() { - Solution obj; - vector<int> c1 = {17, 12, 10, 2, 7, 2, 11, 20, 8}, c2 = {1, 2, 4, 1}; - printf("%lld\n", obj.totalCost(c1, 3, 4)); // expect: 11 - printf("%lld\n", obj.totalCost(c2, 3, 3)); // expect: 4 -} |