1. Every selected worker must receive at least their minimum wage expectation.
2. Pay must be strictly proportional to quality within the selected group.

We must determine the minimum total cost required to hire a valid group of $k$ workers.

Brute Force Approach for Minimum Cost to Hire K Workers

A brute force approach would involve generating every possible combination of $k$ workers from the $n$ available candidates.

For each combination (subset) of $k$ workers:

1. Determine the "group ratio." To satisfy the condition that everyone gets at least their minimum wage, the pay-per-unit-quality ratio for the group must be at least the maximum wage-to-quality ratio among all workers in that subset.
2. Calculate the total cost using this ratio: $Cost = \text{Group Ratio} \times \sum (\text{Quality of workers in subset})$.
3. Track the minimum cost found across all combinations.

Pseudo-code:

text
min_total_cost = infinity
for each subset of size k from n workers:
    current_ratio = 0
    current_quality_sum = 0
    
    // Find the bottleneck ratio
    for worker in subset:
        ratio = worker.wage / worker.quality
        current_ratio = max(current_ratio, ratio)
        current_quality_sum += worker.quality
        
    total_cost = current_ratio * current_quality_sum
    min_total_cost = min(min_total_cost, total_cost)

Complexity Analysis: The number of ways to choose $k$ workers from $n$ is given by the binomial coefficient $\binom{n}{k}$. In the worst case (e.g., $k = n/2$), this grows exponentially.

• Time Complexity: $O(k \cdot \binom{n}{k})$. Given $n=10^4$, this will immediately result in a Time Limit Exceeded (TLE) error.
• Space Complexity: $O(k)$ to store the current subset.

Core Insight for Minimum Cost to Hire K Workers

The key to solving LeetCode 857 efficiently lies in the mathematical relationship between the constraints.

Let $R$ be the ratio of pay to quality. For a worker $i$ to be satisfied, the group ratio $R$ must satisfy: $R \times quality[i] \ge wage[i] \implies R \ge \frac{wage[i]}{quality[i]}$

If we select a group of $k$ workers, the group ratio must be at least the maximum $\frac{wage}{quality}$ ratio among them to satisfy everyone. To minimize cost, we should pick the smallest valid $R$. Therefore, the cost for a specific group is: $Cost = \max_{i \in Group}(\frac{wage[i]}{quality[i]}) \times \sum_{i \in Group} quality[i]$

This equation reveals two greedy strategies:

1. Minimize the Ratio: We should process workers in increasing order of their wage-to-quality ratio. If we fix the worker with the highest ratio in the group (the "captain"), we know exactly what the group ratio is.
2. Minimize the Quality Sum: For a fixed "captain" (who sets the ratio), we want to pair them with $k-1$ other workers who have the smallest possible qualities. Importantly, any worker with a smaller ratio than the captain is a valid candidate.

Visual Description: Imagine sorting all workers on a line based on their unit cost (ratio). As we iterate through this line from left to right, the current worker defines the new maximum ratio allowed. At each step, we have a pool of eligible workers (all seen so far). To minimize cost, we need the $k$ workers with the lowest quality from this pool. A Max-Heap allows us to visualize this pool: the "heaviest" (highest quality) worker floats to the top. When we encounter a new worker, we add them to the pool. If the pool size exceeds $k$, we remove the worker with the highest quality (the root of the heap) because they contribute most to the cost.

Execution Flow

Let's trace the algorithm with quality = [10, 20, 5], wage = [70, 50, 30], k = 2.

1. Calculate Ratios:

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

2. Sort by Ratio:

   • Worker 1: (Ratio: 2.5, Quality: 20)
   • Worker 2: (Ratio: 6.0, Quality: 5)
   • Worker 0: (Ratio: 7.0, Quality: 10)

3. Initialize: max_heap = [], sum_quality = 0, min_cost = Infinity.

4. Iteration 1 (Worker 1):

   • Current Ratio: 2.5
   • Push Quality 20 to heap. max_heap = [20]. sum_quality = 20.
   • Heap size (1) < k (2). Continue.

5. Iteration 2 (Worker 2):

   • Current Ratio: 6.0
   • Push Quality 5 to heap. max_heap = [20, 5]. sum_quality = 25.
   • Heap size (2) == k (2).
   • Calculate Cost: $6.0 \times 25 = 150.0$.
   • min_cost = 150.0.

6. Iteration 3 (Worker 0):

   • Current Ratio: 7.0
   • Push Quality 10 to heap. max_heap = [20, 5, 10]. sum_quality = 35.
   • Heap size (3) > k (2).
   • Pop Max: Remove 20 from heap. max_heap = [10, 5]. sum_quality = 35 - 20 = 15.
   • Heap size is now k (2).
   • Calculate Cost: $7.0 \times 15 = 105.0$.
   • Update min_cost: $\min ($.

7. Result: Return 105.0.

Proof of Correctness

The algorithm's correctness relies on the invariant that at any step $i$ (where we consider the $i$-th worker in the sorted list as the highest-ratio worker), the Max-Heap contains the $k$ smallest qualities encountered in the range $[0, i]$.

Since the list is sorted by ratio, the current worker $i$ has the maximum ratio among all workers currently in the heap. Therefore, calculating ratio[i] * sum(heap_qualities) guarantees that the payment condition is met for all workers in the heap. By consistently evicting the largest quality when the group size exceeds $k$, we ensure that for the specific ratio ratio[i], we are multiplying it by the smallest possible sum of qualities available up to that point. This effectively checks all optimal combinations.

Reference Implementation

C++ Solution for LeetCode 857

cpp
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

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;
        
        // Store ratio and quality. Ratio = wage / quality
        for (int i = 0; i < n; ++i) {
            double ratio = (double)wage[i] / quality[i];
            workers.push_back({ratio, quality[i]});
        }
        
        // Sort by ratio ascending
        sort(workers.begin(), workers.end());
        
        // Max-heap to store qualities of the k workers with smallest qualities so far
        priority_queue<int> max_heap;
        double current_quality_sum = 0;
        double min_total_cost = 1e9 + 7; // Initialize with a large value
        
        for (const auto& worker : workers) {
            double ratio = worker.first;
            int q = worker.second;
            
            current_quality_sum += q;
            max_heap.push(q);
            
            // If we have more than k workers, remove the one with the highest quality
            if (max_heap.size() > k) {
                current_quality_sum -= max_heap.top();
                max_heap.pop();
            }
            
            // If we have exactly k workers, calculate the cost
            if (max_heap.size() == k) {
                min_total_cost = min(min_total_cost, current_quality_sum * ratio);
            }
        }
        
        return min_total_cost;
    }
};

Java Solution for LeetCode 857

java
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Collections;

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] is ratio, workers[i][1] is quality
            workers[i][0] = (double) wage[i] / quality[i];
            workers[i][1] = (double) quality[i];
        }
        
        // Sort by ratio ascending
        Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
        
        // Max-Heap to keep the smallest k qualities (evict largest)
        PriorityQueue<Double> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        double currentQualitySum = 0;
        double minTotalCost = Double.MAX_VALUE;
        
        for (double[] worker : workers) {
            double ratio = worker[0];
            double q = worker[1];
            
            currentQualitySum += q;
            maxHeap.offer(q);
            
            if (maxHeap.size() > k) {
                currentQualitySum -= maxHeap.poll();
            }
            
            if (maxHeap.size() == k) {
                minTotalCost = Math.min(minTotalCost, currentQualitySum * ratio);
            }
        }
        
        return minTotalCost;
    }
}

Python Solution for LeetCode 857

python
import heapq

class Solution:
    def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
        # Create a list of tuples (ratio, quality)
        workers = []
        for q, w in zip(quality, wage):
            workers.append((w / q, q))
            
        # Sort workers by their wage-to-quality ratio
        workers.sort(key=lambda x: x[0])
        
        # Python's heapq is a min-heap. To simulate a max-heap, 
        # we store negative quality values.
        max_heap = []
        current_quality_sum = 0
        min_total_cost = float('inf')
        
        for ratio, q in workers:
            # Add current quality to sum and push negative quality to heap
            current_quality_sum += q
            heapq.heappush(max_heap, -q)
            
            # If we exceed k workers, remove the one with the largest quality
            # (which is the smallest value in our negative heap)
            if len(max_heap) > k:
                largest_quality = -heapq.heappop(max_heap)
                current_quality_sum -= largest_quality
            
            # If we have exactly k workers, calculate cost
            if len(max_heap) == k:
                min_total_cost = min(min_total_cost, current_quality_sum * ratio)
                
        return min_total_cost