Minimum Cost to Hire K Workers

How it works

Every worker has a minimum wage expectation. If we pay workers proportionally to their quality, the worker with the highest wage-to-quality ratio sets the "rate" for the group. Total cost equals rate * total_quality. To minimize cost with a fixed rate, we want workers with the smallest quality values. We sort workers by their rate, then use a max-heap to maintain the k workers with lowest quality seen so far.

Steps

1. Create pairs of (wage/quality ratio, quality) for each worker and sort by ratio.
2. Use a max-heap to track the k smallest qualities.
3. Iterate through workers in order of increasing ratio:
   • Add current worker's quality to heap and running total.
   • If heap size exceeds k, remove the largest quality.
   • When heap size equals k, compute total_quality * current_ratio and track minimum.
4. Return the minimum cost found.

Complexity

• Time complexity: O(n * (log n + log k))
• Space complexity: O(n)

Where n is the number of workers, and k is the number of workers to be hired.

Things to watch for

Misunderstanding the Wage-to-Quality Ratio

The key insight is that the worker with the highest ratio in the chosen group determines the "rate" for everyone. Some mistakenly try to minimize total wage directly or pick workers with the lowest individual wages, missing that all workers must be paid proportionally to their quality based on the maximum ratio in the group.

Using a Min-Heap Instead of a Max-Heap

Once a worker's ratio is fixed as the group's rate, minimizing cost requires selecting workers with the smallest quality values. A max-heap is needed to efficiently remove the worker with the highest quality when the group exceeds size k. Using a min-heap evicts the wrong workers.

Forgetting to Track Running Total Quality

Simply maintaining the heap is not enough. The running sum of qualities in the heap must be tracked separately. Recomputing the sum by iterating through the heap at each step results in O(k) overhead per iteration, degrading overall time complexity.

Computing Cost Before Heap Reaches Size k

The minimum cost should only be computed when exactly k workers are in the heap. Calculating cost with fewer than k workers or updating the result before the heap is properly sized leads to invalid or suboptimal answers.

Integer Division Precision Loss

When computing the wage-to-quality ratio, using integer division truncates the result and loses precision. The ratio must be computed using floating-point division to ensure accurate sorting and cost calculations.

from typing import List
import heapq

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        pairs = sorted([(w / q, q) for q, w in zip(quality, wage)], key=lambda p: p[0])

        maxHeap = []
        total_quality = 0
        res = float("inf")

        for rate, q in pairs:
            heapq.heappush(maxHeap, -q)
            total_quality += q

            if len(maxHeap) > k:
                total_quality += heapq.heappop(maxHeap)

            if len(maxHeap) == k:
                res = min(res, total_quality * rate)

        return res

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<pair<double, int>> workers(n);
        for (int i = 0; i < n; i++) {
            workers[i] = { (double)wage[i] / quality[i], quality[i] };
        }

        sort(workers.begin(), workers.end());
        priority_queue<int> maxHeap;
        double totalQuality = 0, res = DBL_MAX;

        for (auto& worker : workers) {
            double ratio = worker.first;
            int q = worker.second;
            maxHeap.push(q);
            totalQuality += q;

            if (maxHeap.size() > k) {
                totalQuality -= maxHeap.top();
                maxHeap.pop();
            }

            if (maxHeap.size() == k) {
                res = min(res, totalQuality * ratio);
            }
        }

        return res;
    }
};