Minimum cost to hire K workers

Why it matters

A small company wants to hire exactly three contractors for a project. Each contractor has a skill score, which this lesson calls quality, and a minimum daily wage they will accept. The company wants the cheapest total bill that still meets two rules. Each hired contractor must receive at least their minimum wage, and each must be paid in proportion to their quality. A problem like this comes up when pricing teams, staffing agencies and shared resources.

The naive method tries every group of k workers, which becomes too slow when there are many workers. The method in this lesson sorts the workers once and then walks through them in one pass. It uses a greedy choice at each step, plus a heap, which is a data structure that gives the largest item quickly. The result runs in O(n log n) time, a way of writing how the work grows as n, the number of workers, gets larger.

Words you will need

• Quality: a number for how good a worker is. Higher means better.
• Wage: the minimum amount, in money, that a worker will accept.
• Ratio: one number divided by another. Here the ratio of a worker is wage divided by quality.
• Rate: the pay per point of quality. The rate is the same for everyone in a hired group.
• Group: the set of workers the company hires.
• Heap: a data structure that keeps the largest (or smallest) item at the top. You can read the top item quickly, and add or remove items quickly too.
• Max heap: a heap whose top item is the largest. In C++, std::priority_queue<int> is a max heap by default.
• Sum: the total of a list of numbers.
• Double: a C++ type for numbers that can have a fraction part, such as 2.5.

The pay rule

Each hired worker is paid the same rate for each point of quality. Call the rate r. Worker i is paid r times their quality. For a group, the total bill is r times the sum of the group's qualities.

The rate has to be high enough that every worker gets at least their minimum wage. A worker with quality 10 and wage 70 needs a rate of at least 70 divided by 10, which is 7. So the rate for a group must be at least the largest ratio in the group. The cheapest rate is exactly that largest ratio. So the cost of a group is:

largest ratio in the group, times the sum of the qualities in the group

The task now is to pick the group of size k that makes this number smallest.

A worked example by hand

Take three workers.

Hire two of them. The company wants the smallest bill.

Try the group A and C. The largest ratio is 7 (from A), so the rate is 7. The sum of qualities is 10 + 5 = 15. The bill is 7 times 15, which is 105. Check it. A is paid 7 times 10, which is 70, exactly A's wage. C is paid 7 times 5, which is 35, more than C's wage of 30. Both rules hold, and the total is 70 + 35 = 105.

Try the group B and C. The largest ratio is 6 (from C), so the rate is 6. The sum of qualities is 20 + 5 = 25. The bill is 6 times 25, which is 150.

Try the group A and B. The largest ratio is 7. The sum is 30. The bill is 210.

The cheapest of the three groups is A and C, at 105. With only three workers, you can check every group by hand. The next sections show how to find the answer without checking every group.

The brute force method

Brute force means trying every possible answer and keeping the best. For n workers and a group of k, the program below does exactly that. It loops over every subset of workers with k members, and computes the cost of each. A subset is a group. Each worker is one bit in a number, so a number from 0 to 2^n minus 1 names a group.

double brute_force(const std::vector<int>& quality, const std::vector<int>& wage, int k) {
    const int n = static_cast<int>(quality.size());
    double best = 1e18;
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (std::popcount(static_cast<unsigned>(mask)) != k) continue;
        double ratio = 0.0;
        double total_quality = 0.0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                ratio = std::max(ratio, static_cast<double>(wage[i]) / quality[i]);
                total_quality += quality[i];
            }
        }
        best = std::min(best, ratio * total_quality);
    }
    return best;
}

std::popcount counts the 1 bits in mask, which is the group size. The brute force is correct, and the fast method is checked against it later in this lesson. It is too slow for large inputs, because the number of groups grows very fast. With 30 workers and k = 15, there are about 155 million groups.

The key idea

Look at the cost formula again: the largest ratio times the sum of qualities. Suppose we decide which worker has the largest ratio in the group. Call that worker the leader, and call the leader's ratio R. Then the rate is fixed at R. Now the only thing left to choose is the other k - 1 workers, and we want their qualities to add up to the smallest sum. Smaller sum means smaller bill.

Two facts make this work.

1. If we sort the workers by ratio from smallest to largest, then when we reach the leader, every worker before it has a smaller or equal ratio. Those are the only workers the leader can be grouped with, if the leader is to be the largest ratio.
2. Among those earlier workers, we want the k smallest qualities. Keeping the smallest qualities keeps the sum small.

So the method walks the sorted list. At each worker, it asks: if this worker is the leader, what is the cheapest group of k workers from the workers seen so far, including this one? The answer is this worker's ratio times the sum of the k smallest qualities among the workers seen so far, including this one. Keep the smallest of all these answers.

Keeping the k smallest qualities with a heap

To know the sum of the k smallest qualities at each step, we keep a max heap. The heap holds at most k qualities. Its top is the largest quality it holds, so it is easy to throw away the largest when it has too many items.

At each worker:

1. Push its quality into the heap, and add it to the running sum.
2. If the heap now has more than k items, remove the top (the largest quality) and subtract it from the sum.
3. If the heap has exactly k items, the group is ready. Its cost is this worker's ratio times the running sum. Compare it with the best cost so far.

The heap always holds the k smallest qualities seen so far, and the sum always matches the heap.

Worked example 1: the three workers

Sort the workers by ratio. The order is B (2.5), C (6), A (7).

At step 2, the group is B and C, with rate 6 and cost 150. At step 3, A is pushed. The heap now holds 20, 10 and 5, which has three items, one too many. The largest, 20, is removed. The heap holds 10 and 5, with sum 15. The cost is 7 times 15, which is 105. The smallest cost over all steps is 105, the same as the hand check.

The program below solves this in code. It sorts the workers with a lambda, which is a small function written inline. The lambda compares two workers by their ratio.

struct Worker {
    int quality;
    int wage;
    double ratio() const { return static_cast<double>(wage) / quality; }
};
 
double min_cost_to_hire(const std::vector<int>& quality, const std::vector<int>& wage, int k) {
    const std::size_t n = quality.size();
    std::vector<Worker> workers;
    for (std::size_t i = 0; i < n; ++i) {
        workers.push_back({quality[i], wage[i]});
    }
    std::sort(workers.begin(), workers.end(),
              [](const Worker& a, const Worker& b) { return a.ratio() < b.ratio(); });
 
    std::priority_queue<int> max_heap;  // biggest quality on top
    long long quality_sum = 0;
    double best = 1e18;
    for (const Worker& w : workers) {
        max_heap.push(w.quality);
        quality_sum += w.quality;
        if (static_cast<int>(max_heap.size()) > k) {
            quality_sum -= max_heap.top();
            max_heap.pop();
        }
        if (static_cast<int>(max_heap.size()) == k) {
            best = std::min(best, w.ratio() * static_cast<double>(quality_sum));
        }
    }
    return best;
}

Notice that quality_sum is a long long, so the sum cannot overflow for normal inputs. The best cost is a double, because the ratio is a fraction.

Worked example 2: a harder list

Five workers, with k = 3.

The ratios are 1.333, 8, 0.2, 0.2 and 7. Sorted by ratio, the order is worker 3 (0.2), worker 4 (0.2), worker 1 (1.333), worker 5 (7) and worker 2 (8).

The smallest cost is 30.66667, from step 3. At that point the group is workers 3, 4 and 1. The leader is worker 1, with ratio 1.333, and the rate is 1.333. Check the pay. Worker 1 needs 4 and gets 1.333 times 3, which is 4. Worker 3 needs 2 and gets 1.333 times 10, which is 13.33. Worker 4 gets the same, 13.33. Each worker is paid at least the wage, and the total is 30.67.

Running the program on the same input gives the same answer.

Worked example 3: when the heap drops a worker with a low ratio

Three workers, with k = 2:

• Worker X: quality 2, wage 10, ratio 5
• Worker Y: quality 3, wage 9, ratio 3
• Worker Z: quality 6, wage 12, ratio 2

Sorted by ratio: Z (2), Y (3), X (5).

• Step 1: push Z's quality 6. The heap is , with 1 item. No cost yet.
• Step 2: push Y's quality 3. The heap is , sum 9. The cost is 3 times 9, which is 27.
• Step 3: push X's quality 2. The heap is , sum 11. It has 3 items, so remove the top, 6. The heap is , sum 5. The cost is 5 times 5, which is 25.

The best cost is 25. In this example the heap removed worker Z, who had the lowest ratio. That is correct. Worker Z has a large quality, and keeping it would make the sum large. The group Y and X costs less, because the rate is set by X at 5, but the qualities are small.

Brute force on the same input also gives 25.

Common mistakes

Using a min heap. A min heap keeps the smallest item on top. If you use it here, the heap removes the smallest quality, not the largest, and the sum is wrong. The program below uses a min heap, and its answer for the first example is 150, not 105.

Using integer division for the ratio. The ratio must be a fraction. If you write wage / quality with two int values, C++ throws away the fraction and gives a whole number. The program below sorts by that whole number and gets 23 for the second example, which is less than the true minimum of 30.66667. The answer is wrong, and no warning appears.

Forgetting to sort. The method needs the workers in order of ratio, so that the earlier workers have smaller ratios than the leader. Without the sort, the leader may have a small ratio while a larger ratio appears earlier in the list.

A priority queue of workers instead of qualities. This compiles only if the type has an operator<. The compiler gives a long error when it does not. The program below shows the first line of that error.

#include <queue>
 
struct Worker {
    int quality;
    int wage;
};
 
int main() {
    std::priority_queue<Worker> heap;
    heap.push(Worker{10, 70});
    return 0;
}

Compiled with g++ -std=c++20 -Wall, the first error line is:

/usr/include/c++/15/bits/stl_function.h:408:20: error: no match for ‘operator<’ (operand types are ‘const Worker’ and ‘const Worker’)

The path and line number depend on your compiler version. The rest of the message lists several "required from" lines. The fix is to keep the heap of plain int qualities, as the program in this lesson does.

The program below runs the min heap and integer division versions on the two examples.

#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>
 
struct Worker {
    int quality;
    int wage;
    double ratio() const { return static_cast<double>(wage) / quality; }
};
 
// Same as the lesson's solution, but with a min heap (smallest quality on top).
double min_heap_version(const std::vector<int>& quality, const std::vector<int>& wage, int k) {
    std::vector<Worker> workers;
    for (std::size_t i = 0; i < quality.size(); ++i) workers.push_back({quality[i], wage[i]});
    std::sort(workers.begin(), workers.end(),
              [](const Worker& a, const Worker& b) { return a.ratio() < b.ratio(); });
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
    long long sum = 0;
    double best = 1e18;
    for (const Worker& w : workers) {
        heap.push(w.quality);
        sum += w.quality;
        if (static_cast<int>(heap.size()) > k) {
            sum -= heap.top();
            heap.pop();
        }
        if (static_cast<int>(heap.size()) == k) best = std::min(best, w.ratio() * sum);
    }
    return best;
}
 
// Same as the lesson's solution, but with integer division for the ratio.
double integer_ratio_version(const std::vector<int>& quality, const std::vector<int>& wage, int k) {
    std::vector<Worker> workers;
    for (std::size_t i = 0; i < quality.size(); ++i) workers.push_back({quality[i], wage[i]});
    std::sort(workers.begin(), workers.end(),
              [](const Worker& a, const Worker& b) { return a.wage / a.quality < b.wage / b.quality; });
    std::priority_queue<int> heap;
    long long sum = 0;
    double best = 1e18;
    for (const Worker& w : workers) {
        heap.push(w.quality);
        sum += w.quality;
        if (static_cast<int>(heap.size()) > k) {
            sum -= heap.top();
            heap.pop();
        }
        if (static_cast<int>(heap.size()) == k) best = std::min(best, static_cast<double>((w.wage / w.quality) * sum));
    }
    return best;
}
 
int main() {
    std::cout << std::fixed << std::setprecision(5);
    std::cout << "min heap, example 1: " << min_heap_version({10, 20, 5}, {70, 50, 30}, 2) << "\n";
    std::cout << "min heap, example 2: " << min_heap_version({3, 1, 10, 10, 1}, {4, 8, 2, 2, 7}, 3) << "\n";
    std::cout << "integer ratio, example 1: " << integer_ratio_version({10, 20, 5}, {70, 50, 30}, 2) << "\n";
    std::cout << "integer ratio, example 2: " << integer_ratio_version({3, 1, 10, 10, 1}, {4, 8, 2, 2, 7}, 3) << "\n";
    return 0;
}

Its output is:

min heap, example 1: 150.00000
min heap, example 2: 30.66667
integer ratio, example 1: 105.00000
integer ratio, example 2: 23.00000

The integer ratio version gave the right answer for example 1 by luck. For example 2, worker 1 has wage 4 and quality 3, so 4 / 3 is 1 in integer division. The rate becomes 1 instead of 1.333, and the bill looks cheaper than it is. A test with a second example like this one catches the error.

The full solution with a test

The program below is the solution from this lesson, with a test. The test generates 2,000 random inputs, runs both the fast method and the brute force, and counts the mismatches. The random numbers come from std::mt19937, a random number generator, with a fixed seed, so every run uses the same inputs.

#include <algorithm>
#include <bit>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <queue>
#include <random>
#include <vector>
 
struct Worker {
    int quality;
    int wage;
    double ratio() const { return static_cast<double>(wage) / quality; }
};
 
// Greedy with a max heap of qualities.
double min_cost_to_hire(const std::vector<int>& quality, const std::vector<int>& wage, int k) {
    const std::size_t n = quality.size();
    std::vector<Worker> workers;
    for (std::size_t i = 0; i < n; ++i) {
        workers.push_back({quality[i], wage[i]});
    }
    std::sort(workers.begin(), workers.end(),
              [](const Worker& a, const Worker& b) { return a.ratio() < b.ratio(); });
 
    std::priority_queue<int> max_heap;  // biggest quality on top
    long long quality_sum = 0;
    double best = 1e18;
    for (const Worker& w : workers) {
        max_heap.push(w.quality);
        quality_sum += w.quality;
        if (static_cast<int>(max_heap.size()) > k) {
            quality_sum -= max_heap.top();
            max_heap.pop();
        }
        if (static_cast<int>(max_heap.size()) == k) {
            best = std::min(best, w.ratio() * static_cast<double>(quality_sum));
        }
    }
    return best;
}
 
// Brute force: try every group of size k.
double brute_force(const std::vector<int>& quality, const std::vector<int>& wage, int k) {
    const int n = static_cast<int>(quality.size());
    double best = 1e18;
    for (int mask = 0; mask < (1 << n); ++mask) {
        if (std::popcount(static_cast<unsigned>(mask)) != k) continue;
        double ratio = 0.0;
        double total_quality = 0.0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                ratio = std::max(ratio, static_cast<double>(wage[i]) / quality[i]);
                total_quality += quality[i];
            }
        }
        best = std::min(best, ratio * total_quality);
    }
    return best;
}
 
int main() {
    std::cout << std::fixed << std::setprecision(5);
    std::cout << "example 1: " << min_cost_to_hire({10, 20, 5}, {70, 50, 30}, 2) << "\n";
    std::cout << "example 2: " << min_cost_to_hire({3, 1, 10, 10, 1}, {4, 8, 2, 2, 7}, 3) << "\n";
 
    std::mt19937 rng(12345);
    int failures = 0;
    for (int trial = 0; trial < 2000; ++trial) {
        std::uniform_int_distribution<int> n_dist(1, 8);
        int n = n_dist(rng);
        std::uniform_int_distribution<int> k_dist(1, n);
        int k = k_dist(rng);
        std::uniform_int_distribution<int> val(1, 50);
        std::vector<int> q(n), w(n);
        for (int i = 0; i < n; ++i) {
            q[i] = val(rng);
            w[i] = val(rng);
        }
        double a = min_cost_to_hire(q, w, k);
        double b = brute_force(q, w, k);
        if (std::abs(a - b) > 1e-6) {
            ++failures;
        }
    }
    std::cout << "random trials with mismatch: " << failures << " of 2000\n";
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -o hire hire.cpp
./hire

The output is:

example 1: 105.00000
example 2: 30.66667
random trials with mismatch: 0 of 2000

A zero mismatch count over 2,000 random cases is strong evidence. The random inputs can differ between C++ libraries, but the count should be 0 on any system. It is not a proof, but the brute force and the fast method use different ideas, so agreement on many inputs is a good sign.

Practice

Exercise 1. Two workers have quality 4 and wage 20, and quality 6 and wage 24. Find the cost of hiring both.

Show the answer

The ratios are 20 / 4 = 5 and 24 / 6 = 4. The largest is 5, so the rate is 5. The sum of qualities is 4 + 6 = 10. The cost is 5 times 10, which is 50. Check it: the first worker gets 5 times 4 = 20, exactly the wage. The second gets 5 times 6 = 30, more than the wage of 24.

Exercise 2. The function is called with k = 1. What does it return, and why?

Show the answer

It returns the smallest wage in the list. With one worker, the rate is that worker's ratio, and the pay is the rate times the worker's quality. That equals the worker's wage. Any group of one worker costs exactly that worker's wage, so the lowest wage wins. The first worker in the example list has wage 70, the second 50 and the third 30, so the function returns 30 for k = 1.

Exercise 3. Someone changes the heap to keep the k largest qualities by removing the smallest instead. Explain in plain words why the answer becomes wrong.

Show the answer

The rate is fixed by the leader's ratio. The only choice left is which other workers to add. Adding large qualities makes the sum bigger, so the bill goes up. The method needs the k smallest qualities, because the smallest sum gives the smallest bill for a fixed rate. Keeping the largest qualities gives a bill that is too high.

Exercise 4. Qualities are 5, 5 and 5. Wages are 10, 20 and 30. Find the cheapest group of two.

Show the answer

Check each pair. Workers 1 and 2 have ratios 2 and 4, so the rate is 4, and the sum of qualities is 10. The cost is 40. Workers 1 and 3 have ratios 2 and 6, so the rate is 6, and the cost is 60. Workers 2 and 3 have ratios 4 and 6, so the rate is 6, and the cost is 60. The cheapest is 40, from workers 1 and 2.

Summary

• Each hired worker is paid the same rate per point of quality, and the rate must be at least every worker's wage divided by quality.
• The cost of a group is its largest ratio times the sum of its qualities.
• Sort workers by ratio, then walk the list. At each worker, treat it as the leader and use the smallest qualities seen so far.
• A max heap of at most k qualities, with a running sum, gives those smallest qualities in O(log k) time per step.
• Use a double for the ratio, and a max heap of plain qualities, not workers.