aboutsummaryrefslogtreecommitdiff
path: root/cost_hire_k_worker.c
diff options
context:
space:
mode:
Diffstat (limited to 'cost_hire_k_worker.c')
-rw-r--r--cost_hire_k_worker.c195
1 files changed, 195 insertions, 0 deletions
diff --git a/cost_hire_k_worker.c b/cost_hire_k_worker.c
new file mode 100644
index 0000000..bd1ba3c
--- /dev/null
+++ b/cost_hire_k_worker.c
@@ -0,0 +1,195 @@
+// 2462. Total Cost to Hire K Workers
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.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.
+ */
+
+typedef struct {
+ int val;
+ int idx;
+} node;
+
+int cmp(const void *a, const void *b) {
+ node *A = *(node **)a;
+ node *B = *(node **)b;
+ return A->val - B->val;
+}
+void swap(node **a, node **b) {
+ node *tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+void modifyHeap(node **heap, int n) {
+ int f = 0;
+ while (1) {
+ int c1 = 2 * f + 1;
+ int c2 = 2 * f + 2;
+ if (c2 < n) {
+ if (heap[c1]->val <= heap[c2]->val) {
+ if (heap[c1]->val < heap[f]->val) {
+ swap(&heap[f], &heap[c1]);
+ f = c1;
+ } else
+ break;
+ } else {
+ if (heap[c2]->val < heap[f]->val) {
+ swap(&heap[f], &heap[c2]);
+ f = c2;
+ } else
+ break;
+ }
+ } else if (c1 < n) {
+ if (heap[c1]->val < heap[f]->val) {
+ swap(&heap[f], &heap[c1]);
+ f = c1;
+ } else
+ break;
+ } else
+ break;
+ }
+}
+int heapPop(node **heap, int *n) {
+ int ans = heap[0]->val;
+ *n = *n - 1;
+ heap[0] = heap[*n];
+
+ int f = 0;
+ int N = *n;
+ while (1) {
+ int c1 = 2 * f + 1;
+ int c2 = 2 * f + 2;
+ if (c2 < N) {
+ if (heap[c1]->val <= heap[c2]->val) {
+ if (heap[f]->val > heap[c1]->val) {
+ swap(&heap[f], &heap[c1]);
+ f = c1;
+ continue;
+ } else
+ break;
+ } else {
+ if (heap[f]->val > heap[c2]->val) {
+ swap(&heap[f], &heap[c2]);
+ f = c2;
+ continue;
+ } else
+ break;
+ }
+ } else if (c1 < N) {
+ if (heap[f]->val > heap[c1]->val) {
+ swap(&heap[f], &heap[c1]);
+ f = c1;
+ continue;
+ } else
+ break;
+ } else
+ break;
+ }
+ return ans;
+}
+long long totalCost(int *costs, int costsSize, int k, int candidates) {
+ int n = costsSize;
+ int left_cn = candidates;
+ int right_cn = candidates;
+
+ if ((left_cn + right_cn) > n) {
+ left_cn = n / 2;
+ right_cn = n - n / 2;
+ }
+
+ long long ans = 0;
+ if (k == costsSize) {
+ for (int i = 0; i < costsSize; i++) {
+ ans = ans + costs[i];
+ }
+ return ans;
+ }
+
+ bool *used = calloc(n, sizeof(bool));
+ node **left = malloc(left_cn * sizeof(node *));
+ node **right = malloc(right_cn * sizeof(node *));
+ for (int i = 0; i < left_cn; i++) {
+ left[i] = malloc(sizeof(node));
+ left[i]->val = costs[i];
+ left[i]->idx = i;
+ used[i] = true;
+ }
+ for (int i = 0; i < right_cn; i++) {
+ right[i] = malloc(sizeof(node));
+ right[i]->val = costs[n - 1 - i];
+ right[i]->idx = n - 1 - i;
+ used[n - 1 - i] = true;
+ }
+ qsort(left, left_cn, sizeof(node *), cmp);
+ qsort(right, right_cn, sizeof(node *), cmp);
+ int l_idx = left_cn;
+ int r_idx = n - 1 - right_cn;
+
+ int item = 0;
+ while (item < k) {
+ if (left_cn == 0) {
+ ans += heapPop(right, &right_cn);
+ item++;
+ continue;
+ }
+ if (right_cn == 0) {
+ ans += heapPop(left, &left_cn);
+ item++;
+ continue;
+ }
+ if (left[0]->val == right[0]->val && left[0]->idx == right[0]->idx) {
+ ans += left[0]->val;
+ heapPop(left, &left_cn);
+ heapPop(right, &right_cn);
+ } else if (left[0]->val <= right[0]->val) {
+ ans += left[0]->val;
+ if (used[l_idx])
+ heapPop(left, &left_cn);
+ else {
+ left[0]->val = costs[l_idx];
+ left[0]->idx = l_idx;
+ used[l_idx] = true;
+ l_idx++;
+ modifyHeap(left, left_cn);
+ }
+ } else {
+ ans += right[0]->val;
+ if (used[r_idx]) {
+ heapPop(right, &right_cn);
+ } else {
+ right[0]->val = costs[r_idx];
+ right[0]->idx = r_idx;
+ used[r_idx] = true;
+ r_idx--;
+ modifyHeap(right, right_cn);
+ }
+ }
+ item++;
+ }
+ free(used);
+ for (int i = 0; i < right_cn; i++)
+ free(right[i]);
+ for (int i = 0; i < left_cn; i++)
+ free(left[i]);
+ free(left);
+ free(right);
+ return ans;
+}
+
+int main() {
+ int c1[] = {17, 12, 10, 2, 7, 2, 11, 20, 8}, c2[] = {1, 2, 4, 1};
+ printf("%lld\n", totalCost(c1, 9, 3, 4)); // expect: 11
+ printf("%lld\n", totalCost(c2, 4, 3, 3)); // expect: 4
+}