From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- cost_hire_k_worker.cpp | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) create mode 100644 cost_hire_k_worker.cpp (limited to 'cost_hire_k_worker.cpp') diff --git a/cost_hire_k_worker.cpp b/cost_hire_k_worker.cpp new file mode 100644 index 0000000..5bb0860 --- /dev/null +++ b/cost_hire_k_worker.cpp @@ -0,0 +1,48 @@ +// 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 &costs, int k, int candidates) { + int i = 0, j = costs.size() - 1; + priority_queue, greater> 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 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 +} -- cgit v1.2.3