Minimum Cost to Hire K Workers
Problem
There are n workers. Worker i has a quality[i] and a minimum wage expectation wage[i]. Hire exactly k workers forming a paid group under two rules: every worker is paid in proportion to their quality relative to the rest of the group, and every worker must receive at least their minimum wage. Return the least total amount needed.
quality = [10, 20, 5], wage = [70, 50, 30], k = 2105.00000import heapq
def mincost_to_hire_workers(quality, wage, k):
workers = sorted((w / q, q) for w, q in zip(wage, quality))
heap, sum_q, best = [], 0, float('inf')
for ratio, q in workers:
heapq.heappush(heap, -q)
sum_q += q
if len(heap) > k:
sum_q += heapq.heappop(heap)
if len(heap) == k:
best = min(best, ratio * sum_q)
return bestfunction mincostToHireWorkers(quality, wage, k) {
const workers = quality.map((q, i) => [wage[i] / q, q])
.sort((a, b) => a[0] - b[0]);
const heap = new MaxHeap();
let sumQ = 0, best = Infinity;
for (const [ratio, q] of workers) {
heap.push(q); sumQ += q;
if (heap.size() > k) sumQ -= heap.pop();
if (heap.size() === k) best = Math.min(best, ratio * sumQ);
}
return best;
}double mincostToHireWorkers(int[] quality, int[] wage, int k) {
int n = quality.length;
double[][] workers = new double[n][2];
for (int i = 0; i < n; i++)
workers[i] = new double[]{ (double) wage[i] / quality[i], quality[i] };
Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
double sumQ = 0, best = Double.MAX_VALUE;
for (double[] wk : workers) {
heap.add((int) wk[1]); sumQ += wk[1];
if (heap.size() > k) sumQ -= heap.poll();
if (heap.size() == k) best = Math.min(best, wk[0] * sumQ);
}
return best;
}double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
int n = quality.size();
vector<pair<double,int>> workers;
for (int i = 0; i < n; i++)
workers.push_back({ (double) wage[i] / quality[i], quality[i] });
sort(workers.begin(), workers.end());
priority_queue<int> heap;
double sumQ = 0, best = 1e18;
for (auto& [ratio, q] : workers) {
heap.push(q); sumQ += q;
if ((int) heap.size() > k) { sumQ -= heap.top(); heap.pop(); }
if ((int) heap.size() == k) best = min(best, ratio * sumQ);
}
return best;
}Explanation
Everyone in the group is paid in proportion to their quality, and nobody can earn below their minimum wage. The pay rate the whole group must use is set by the worker with the highest wage-to-quality ratio. So total cost = ratio × (sum of group qualities).
That gives a plan: sort workers by their wage/quality ratio ascending. As we sweep, the current worker has the largest ratio so far, so it sets the group's pay rate. Every worker before them is cheaper per unit of quality and may join.
Given the rate is fixed, we want the smallest total quality for the remaining members. We keep a max-heap of qualities with a running sumQ; when it holds more than k, we pop the largest quality so only the k smallest remain.
Whenever the heap holds exactly k workers, the candidate cost is ratio × sumQ, and we keep the minimum across all sweep positions.
Example: quality=[10,20,5], wage=[70,50,30], k=2. Choosing workers 0 and 2 sets the rate and yields pays of 70 and 35, total 105 — the cheapest valid group.