aboutsummaryrefslogtreecommitdiff
path: root/cost_hire_k_worker.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /cost_hire_k_worker.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'cost_hire_k_worker.cpp')
-rw-r--r--cost_hire_k_worker.cpp48
1 files changed, 48 insertions, 0 deletions
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<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
+}