← Back to Index

📚 Minimum Cost to Hire K Workers – Java Cheat Sheet

📌 What Is It?

The Minimum Cost to Hire K Workers problem involves hiring exactly K workers from a pool of workers, each with a given quality and wage. The goal is to minimize the total cost while ensuring that every worker is paid at least their minimum wage.

This problem can be solved using a min-heap to track the workers with the lowest quality-to-wage ratio.

🧱 Pattern Template

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        Worker[] workers = new Worker[n];
        for (int i = 0; i < n; i++) {
            workers[i] = new Worker(quality[i], wage[i]);
        }

        Arrays.sort(workers, (a, b) -> Double.compare(a.ratio, b.ratio));

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int qualitySum = 0;
        double minCost = Double.MAX_VALUE;

        for (Worker worker : workers) {
            maxHeap.offer(worker.quality);
            qualitySum += worker.quality;

            if (maxHeap.size() > k) {
                qualitySum -= maxHeap.poll();
            }

            if (maxHeap.size() == k) {
                minCost = Math.min(minCost, qualitySum * worker.ratio);
            }
        }

        return minCost;
    }

    class Worker {
        int quality;
        double ratio;

        Worker(int quality, int wage) {
            this.quality = quality;
            this.ratio = (double) wage / quality;
        }
    }
}

📊 Time Complexity

• Sorting Workers: O(N log N) – Sorting workers by their quality-to-wage ratio.
• Heap Operations: O(N log K) – Adding and removing elements from the heap.
• Overall Complexity: O(N log N + N log K).

✅ Use Cases

• Optimizing costs in hiring scenarios
• Applications in resource allocation problems
• Efficiently processing large datasets

📘 Common LeetCode Problems

• 857. Minimum Cost to Hire K Workers [Hard] Heap

🧪 Example: Minimum Cost to Hire K Workers

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000

Explanation:
- Hire workers with quality [20, 5].
- The minimum cost is 105.

▶️ View Animation

💡 Pro Tips

• Sort workers by their quality-to-wage ratio to ensure fairness.
• Use a max-heap to efficiently track the highest quality workers.
• Edge cases: fewer than K workers, workers with identical ratios.