Problem Description

You are given two arrays: quality and wage, where quality[i] represents the quality of the i-th worker, and wage[i] is the minimum wage expectation for the i-th worker. You want to hire exactly K workers out of the n available. When you hire a group of workers, you must pay each worker in the group the same wage per unit of quality, and this wage must be at least as high as each worker's minimum wage expectation.

Your goal is to choose exactly K workers such that the total wage paid to them is minimized.

Constraints:

• Each worker must be paid at least their minimum wage expectation.
• All selected workers must be paid the same wage per unit quality.
• Each worker can be used at most once (no reuse).
• There is always at least one valid solution.

Thought Process

At first glance, you might think about checking all combinations of K workers and calculating the total wage for each group. However, this brute-force approach is computationally expensive, especially as the number of workers increases.

The challenge arises because each worker has both a quality and a minimum wage, and the group must be paid with a uniform wage per quality. This means the highest wage-to-quality ratio among the chosen workers determines the rate for all.

The key insight is to realize that for any group of K workers, the total wage is the sum of their qualities multiplied by the maximum wage-to-quality ratio among them. So, if we pick a worker as the "pivot" (the one with the highest wage-to-quality ratio in the group), we can compute the minimum cost for that group.

To optimize, we want the smallest sum of qualities among groups whose highest wage-to-quality ratio is as low as possible.

Solution Approach

We can solve this problem efficiently using the following steps:

1. Calculate wage-to-quality ratios: For each worker, compute ratio = wage[i] / quality[i]. This ratio represents the minimum "wage per quality" the worker is willing to accept.
2. Sort workers by ratio: Sort all workers in ascending order of their ratio.
3. Iterate through sorted workers: As we process each worker in order of increasing ratio, consider each as the potential "pivot" (the highest ratio in a group).
4. Keep a running set of the K smallest qualities: Use a max-heap (priority queue) to keep track of the K smallest qualities seen so far. This is because, for a given ratio, the minimum total wage is achieved by combining the smallest qualities with that ratio.
5. Calculate total cost: For each step where we have K workers, calculate the total cost as sum_of_qualities * current_ratio. Track the minimum among these.

Example Walkthrough

Example:
quality = [10, 20, 5], wage = [70, 50, 30], K = 2

Step 1: Compute ratios:

• Worker 0: 70 / 10 = 7.0
• Worker 1: 50 / 20 = 2.5
• Worker 2: 30 / 5 = 6.0

• Add Worker 1 (quality=20), heap=[20], sum=20
• Add Worker 2 (quality=5), heap=[20,5], sum=25 (Now K=2)
  • Current ratio=6.0, cost=25*6.0=150
• Add Worker 0 (quality=10), heap=[20,5,10], sum=35. Remove largest (20), heap=[10,5], sum=15
  • Current ratio=7.0, cost=15*7.0=105

Time and Space Complexity

Brute-force approach: Try all possible combinations of K workers. There are C(n, K) combinations, and for each, we compute the cost. This is O(n^K), which is infeasible for large n.

Optimized approach:

• Sorting the workers: O(n log n)
• For each worker, heap operations (push/pop): O(log K) per worker, O(n log K) total

Summary

This problem is elegantly solved by recognizing that the highest wage-to-quality ratio among chosen workers determines the pay rate for all, and that minimizing the sum of qualities for each candidate ratio yields the lowest cost. By sorting workers and greedily maintaining the smallest qualities with a heap, we achieve an efficient and optimal solution.

The key insight is to decouple the problem into managing ratios and qualities, and to use efficient data structures (sorting and heaps) to minimize the overall wage.

Code Implementation

import heapq

class Solution:
    def mincostToHireWorkers(self, quality, wage, K):
        workers = sorted(
            [(w / q, q) for q, w in zip(quality, wage)]
        )
        heap = []
        sumq = 0
        res = float('inf')
        for ratio, q in workers:
            heapq.heappush(heap, -q)
            sumq += q
            if len(heap) > K:
                sumq += heapq.heappop(heap)
            if len(heap) == K:
                res = min(res, sumq * ratio)
        return res
      

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    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> maxHeap;
        int sumq = 0;
        double res = 1e9;
        for (auto& w : workers) {
            maxHeap.push(w.second);
            sumq += w.second;
            if (maxHeap.size() > K) {
                sumq -= maxHeap.top();
                maxHeap.pop();
            }
            if (maxHeap.size() == K) {
                res = min(res, sumq * w.first);
            }
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public 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][0] = (double) wage[i] / quality[i];
            workers[i][1] = quality[i];
        }
        Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int sumq = 0;
        double res = Double.MAX_VALUE;
        for (double[] w : workers) {
            maxHeap.offer((int) w[1]);
            sumq += (int) w[1];
            if (maxHeap.size() > K) {
                sumq -= maxHeap.poll();
            }
            if (maxHeap.size() == K) {
                res = Math.min(res, sumq * w[0]);
            }
        }
        return res;
    }
}
      

/**
 * @param {number[]} quality
 * @param {number[]} wage
 * @param {number} K
 * @return {number}
 */
var mincostToHireWorkers = function(quality, wage, K) {
    let workers = [];
    for (let i = 0; i < quality.length; ++i) {
        workers.push([wage[i] / quality[i], quality[i]]);
    }
    workers.sort((a, b) => a[0] - b[0]);
    let heap = [];
    let sumq = 0, res = Infinity;
    function pushHeap(val) {
        heap.push(val);
        heap.sort((a, b) => b - a);
    }
    function popHeap() {
        return heap.shift();
    }
    for (let [ratio, q] of workers) {
        pushHeap(q);
        sumq += q;
        if (heap.length > K) {
            sumq -= popHeap();
        }
        if (heap.length == K) {
            res = Math.min(res, sumq * ratio);
        }
    }
    return res;
};