Minimum Cost to Hire K Workers

[!NOTE] This is a classic “Constraint Optimization” problem. We must satisfy two rules:

Minimum wage expectation.

Pay directly proportional to quality. These rules together imply: Every worker in the group is paid according to the highest wage/quality ratio in that group.

1. Problem Definition

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the $i^{th}$ worker and wage[i] is the minimum wage expectation.

You want to hire exactly k workers such that:

Every worker is paid at least their minimum wage.
Pay is proportional to quality.

Return the least amount of money needed.

Example:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation:
- Worker 0 Ratio: $70/10 = 7.0$
- Worker 1 Ratio: $50/20 = 2.5$
- Worker 2 Ratio: $30/5 = 6.0$
- If we hire {0, 2}, the max ratio is 7.0. Total Quality: $10+5=15$. Cost: $15 \times 7 = 105$.

2. Interactive Analysis

Visualize how the Current Ratio and Total Quality combine to create the cost. Watch how the Max-Heap helps us discard the most “expensive” (highest quality) workers to keep the sum low.

Available Workers (Sorted by Ratio)

Current Paid Group (Size K=3)

Total Quality: 0

Current Ratio: 0.00

Total Cost: ∞

Process workers one by one. The current worker defines the ratio boundary.

3. Intuition

The Core Math

To satisfy the “proportional to quality” rule, if we decide on a unit ratio $R$ (wage per quality), every worker $i$ in our group gets paid $Quality_i \times R$. To satisfy the “minimum wage” rule, we must have $Quality_i \times R \ge Wage_i$, which means $R \ge \frac{Wage_i}{Quality_i}$.

Thus, for a group of $K$ workers, the unit ratio $R$ must be at least the maximum ratio among all $K$ workers. To minimize cost, we pick $R = \max(r_1, r_2, \dots, r_k)$.

Total Cost = $\sum_{i=1}^K (Quality_i \times R) = R \times \sum Quality_i$.

Approach 1: Brute Force ( Fix the Ratio)

Try every single worker $i$ as the “Ratio Boundary” (the one with the maximum ratio in the group).
For this worker $i$, find all other workers whose ratio is $\le r_i$.
Among these compatible workers, pick the $K-1$ workers with the smallest qualities.
Calculate cost and keep the minimum.
- Complexity: $O(N^2 \log N)$ (Iterate $N$ workers, sort compatible workers by quality).
- Limit: $N=10^4$, so $N^2 = 10^8$, which might TLE.

Approach 2: Optimized (Sliding Window + Max Heap)

Instead of re-finding the best $K-1$ workers for every ratio, notice that as we increase the ratio boundary (by sorting workers by ratio), the set of “compatible” workers only grows.

Sort all workers by their wage/quality ratio.
Iterate through workers. As you move, the current worker’s ratio is your $R$.
Add the current worker’s quality to a sum.
Use a Max-Heap to store the qualities of workers in the current group.
If the group size exceeds $K$, remove the largest quality from the sum and the heap. (This is greedy: since the ratio is fixed by the current pointer, the only way to reduce cost is to reduce the total quality).
- Complexity: $O(N \log N)$ for sorting + $O(N \log K)$ for heap operations.

4. Solutions

Java

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Worker[] workers = new Worker[n];
        
        // Step 1: Calculate ratios and store with quality
        for (int i = 0; i < n; i++) {
            workers[i] = new Worker((double) wage[i] / quality[i], quality[i]);
        }
        
        // Step 2: Sort by ratio boundary
        Arrays.sort(workers, (a, b) -> Double.compare(a.ratio, b.ratio));
        
        // Step 3: Max-Heap to keep the K smallest qualities
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        double minCost = Double.MAX_VALUE;
        int qualitySum = 0;
        
        for (Worker worker : workers) {
            qualitySum += worker.quality;
            maxHeap.offer(worker.quality);
            
            // If we have more than K workers, remove the one with highest quality
            if (maxHeap.size() > k) {
                qualitySum -= maxHeap.poll();
            }
            
            // If we have exactly K workers, the current worker's ratio is the max ratio
            if (maxHeap.size() == k) {
                minCost = Math.min(minCost, qualitySum * worker.ratio);
            }
        }
        
        return minCost;
    }
    
    private static class Worker {
        double ratio;
        int quality;
        
        Worker(double ratio, int quality) {
            this.ratio = ratio;
            this.quality = quality;
        }
    }
}

import (
    "container/heap"
    "math"
    "sort"
)

type Worker struct {
    ratio   float64
    quality int
}

// MaxHeap for quality
type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] } // Max-Heap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}){ *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func mincostToHireWorkers(quality []int, wage []int, k int) double {
    n := len(quality)
    workers := make([]Worker, n)
    for i := 0; i < n; i++ {
        workers[i] = Worker{float64(wage[i]) / float64(quality[i]), quality[i]}
    }

    // Sort workers by ratio
    sort.Slice(workers, func(i, j int) bool {
        return workers[i].ratio < workers[j].ratio
    })

    maxHeap := &IntHeap{}
    heap.Init(maxHeap)
    
    qualitySum := 0
    minCost := math.MaxFloat64

    for _, worker := range workers {
        qualitySum += worker.quality
        heap.Push(maxHeap, worker.quality)

        if maxHeap.Len() > k {
            qualitySum -= heap.Pop(maxHeap).(int)
        }

        if maxHeap.Len() == k {
            cost := float64(qualitySum) * worker.ratio
            if cost < minCost {
                minCost = cost
            }
        }
    }

    return minCost
}

5. Complexity Analysis

Strategy	Time Complexity	Space Complexity	Why it matters
Brute Force	$O(N^2 \log N)$	$O(N)$	Simple but too slow for $10^4$ workers.
Sorting + Max-Heap	$O(N \log N)$	$O(N)$	Handles large inputs by greedily maintaining the lowest total quality.