aboutsummaryrefslogtreecommitdiff
path: root/min_cost_hire_k_worker.c
blob: b276c739a5140238236ec25a4a3a38a9c2f4c783 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// 857. Minimum Cost to Hire K Workers
#include "leetcode.h"

/*
 * there are 'n' workers. you are given two integer arrays 'quality' and 'wage'
 * where 'quality[i]' is the quality of the i'th worker and 'wage[i]' is the
 * minimum wage expectation for the i'th worker. we want to hire exactly 'k'
 * workers to form a paid group. to hire a group of 'k' workers, we must pay
 * them according to the following rules. every worker in the paid group must be
 * paid at least their minimum wage expectation. in the group, each worker's pay
 * must be directly proportional to their quality. this means if a worker's
 * quality is double that of another worker in the group, then they must be paid
 * twice as much as the other worker. given the integer 'k', return the least
 * amount of money needed to form apaid group satisfying the above conditions.
 */

struct workers {
  int q;
  int w;
  double w_p_q;
};

int cmp_work(const void *a, const void *b) {
  double tmp = ((struct workers *)b)->w_p_q - ((struct workers *)a)->w_p_q;
  if (tmp < 0)
    return -1;
  return 1;
}

int cmp(const void *a, const void *b) { return *(int *)b - *(int *)a; }

void max_heap_insert(int *heap, int *n, int val) {
  int i = ++(*n), parent = i / 2;
  while (i != 1 && val > heap[parent]) {
    heap[i] = heap[parent];
    i = parent;
    parent /= 2;
  }
  heap[i] = val;
}

int max_heap_delete(int *heap, int *n) {
  int val = heap[1], tmp = heap[*n--], parent = 1, child = parent * 2;
  while (child <= *n) {
    if (child < *n && heap[child] < heap[child + 1])
      child++;
    if (tmp >= heap[child])
      break;
    else {
      heap[parent] = heap[child];
      parent = child;
      child *= 2;
    }
  }
  heap[parent] = tmp;
  return val;
}

void get_dp(struct workers *arr, int size, int num, int *dp) {
  if (!num)
    return;
  int tmp[num + 1], n = 0, sum = 0;
  for (int i = size - num; i < size; i++) {
    max_heap_insert(tmp, &n, arr[i].q);
    sum += arr[i].q;
  }
  dp[size - num] = sum;
  for (int i = size - num - 1; i >= 0; i--) {
    if (arr[i].q < tmp[1]) {
      sum -= max_heap_delete(tmp, &n);
      sum += arr[i].q;
      max_heap_insert(tmp, &n, arr[i].q);
    }
    dp[i] = sum;
  }
}

double mincostToHireWorkers(int *quality, int qualitySize, int *wage,
                            int wageSize, int k) {
  if (qualitySize == 1)
    return wage[0];
  struct workers *member =
      (struct workers *)malloc(qualitySize * sizeof(struct workers));
  for (int i = 0; i < qualitySize; i++) {
    member[i].q = quality[i];
    member[i].w = wage[i];
    member[i].w_p_q = (double)wage[i] / quality[i];
  }
  double ans = 1000000000, cost;
  int max = 0x7fffffff, q_idx = 0, dp[qualitySize];
  qsort(member, qualitySize, sizeof(struct workers), cmp_work);
  get_dp(member, qualitySize, k - 1, dp);
  for (int i = 0; i <= qualitySize - k; i++) {
    int total = member[i].q;
    if (k != 1)
      total += dp[i + 1];
    cost = total * member[i].w_p_q;
    if (cost < ans)
      ans = cost;
  }
  return ans;
}

int main() {
  int q1[] = {10, 20, 5}, w1[] = {70, 50, 30}, q2[] = {3, 1, 10, 10, 1},
      w2[] = {4, 8, 2, 2, 7};
  printf("%f\n", mincostToHireWorkers(q1, ARRAY_SIZE(q1), w1, ARRAY_SIZE(w1),
                                      2)); // expect: 105.0000
  printf("%f\n", mincostToHireWorkers(q2, ARRAY_SIZE(q2), w2, ARRAY_SIZE(w2),
                                      3)); // expect: 30.6667
}