Minimum Cost to Hire K Workers

HardGreedy · Sorting · Heap🧩 Greedy LeetCode #857 ↗Updated Oct 30, 2026

Problem

Worker i has a skill level quality[i] and a minimum acceptable pay wage[i]. Hire exactly k workers so that (1) everyone in the group is paid in proportion to their quality and (2) nobody gets less than their minimum. Return the lowest total pay for such a group (answers within 10^-5 are accepted).

Inputquality = [10,20,5], wage = [70,50,30], k = 2Output105.0 (pay 70 and 35)

Inputquality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3Output30.66667

1 ≤ k ≤ n ≤ 10⁴ · 1 ≤ quality[i], wage[i] ≤ 10⁴

Try it yourself

Java

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Proportional pay means one shared rate (pay per unit of quality). The rate must cover the largest wage/quality ratio in the group, so cost = maxRatio × sumQuality. Sort by ratio, let each worker be the “captain” who sets the rate, and keep the k smallest qualities seen so far in a max-heap.

PatternGreedy

Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.

Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.

Open the Greedy guide →

Approaches

Brute ForceTry Every Group of k

Time O(C(n,k) · k)Space O(k)

For a fixed group the cheapest valid rate is its largest wage[i]/quality[i], so the group costs maxRatio × sum(quality). Enumerate every k-subset with recursion, tracking the running sum and max ratio, and keep the minimum.

Java

private double best;

public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    best = Double.MAX_VALUE;
    choose(quality, wage, k, 0, 0, 0, 0.0);
    return best;
}

private void choose(int[] q, int[] w, int k, int start, int picked, long sumQ, double maxR) {
    if (picked == k) {
        best = Math.min(best, sumQ * maxR);
        return;
    }
    for (int i = start; i <= q.length - (k - picked); i++) {
        double ratio = (double) w[i] / q[i];
        choose(q, w, k, i + 1, picked + 1, sumQ + q[i], Math.max(maxR, ratio));
    }
}

Establishes the cost formula, but combinatorial — hopeless beyond tiny n.

BetterFix the Captain, Take k Smallest Qualities

Time O(n² log n)Space O(n)

Guess which worker sets the rate (the captain). Anyone whose ratio is no larger can join at that rate, and to minimise rate × sum we take the k smallest qualities among them. Trying every captain covers the optimal group, because its own max-ratio worker is one of the guesses.

Java

public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    int n = quality.length;
    double best = Double.MAX_VALUE;
    for (int c = 0; c < n; c++) {
        List<Integer> pool = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            // ratio[j] <= ratio[c], compared without division
            if ((long) wage[j] * quality[c] <= (long) wage[c] * quality[j]) {
                pool.add(quality[j]);
            }
        }
        if (pool.size() < k) continue;
        Collections.sort(pool);
        long sum = 0;
        for (int i = 0; i < k; i++) sum += pool.get(i);
        best = Math.min(best, sum * ((double) wage[c] / quality[c]));
    }
    return best;
}

Polynomial thanks to the captain idea, but re-sorts candidates for every captain.

OptimalSort by Ratio + Max-Heap of Qualities

Time O(n log n)Space O(n)

Process workers in increasing ratio order, so the current worker is always a valid captain for everyone before them. Maintain a max-heap of the k smallest qualities seen so far and their sum: push the new quality, and if the heap exceeds k, pop the largest. With exactly k in the heap, sum × currentRatio is a candidate answer.

Java

public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    int n = quality.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    // ascending wage/quality, compared exactly via cross-multiplication
    Arrays.sort(order, (a, b) ->
        Long.compare((long) wage[a] * quality[b], (long) wage[b] * quality[a]));

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    long sumQ = 0;
    double best = Double.MAX_VALUE;
    for (int i : order) {
        maxHeap.offer(quality[i]);
        sumQ += quality[i];
        if (maxHeap.size() > k) sumQ -= maxHeap.poll(); // drop the largest quality
        if (maxHeap.size() == k) {
            best = Math.min(best, sumQ * ((double) wage[i] / quality[i]));
        }
    }
    return best;
}

One sort plus one heap sweep — the expected Hard-level solution.

Pro tip

If the popped quality is the captain's own, the candidate is merely an over-estimate — still a valid group — so correctness is unaffected.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Group of k	`O(C(n,k) · k)`	`O(k)`
Better	Fix the Captain, Take k Smallest Qualities	`O(n² log n)`	`O(n)`
Optimal	Sort by Ratio + Max-Heap of Qualities	`O(n log n)`	`O(n)`

Common pitfalls

Sorting by wage or by quality alone — the group cost depends on the ratio.
Integer division in wage / quality — cast to double first.
Using a min-heap: you must evict the largest quality to keep the sum small.

Interview tips

Derive cost = maxRatio × sumQuality first; everything else follows from it.
Frame it as “fix one parameter (the captain), optimise the rest greedily”.
Mention the cross-multiplication comparator to avoid floating-point sort issues.

Pattern

Sort by one key + heap on another → cost = (max of A) × (sum of B) over a size-k group.

My notes saved in this browser