LeetCode 857: Minimum Cost to Hire K Workers Solution

Master LeetCode problem 857 (Minimum Cost to Hire K Workers), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

857. Minimum Cost to Hire K Workers

Hard

Array Greedy Sorting Heap (Priority Queue)

Problem Explanation

Explanation

To solve this problem, we need to find the minimum cost to hire exactly k workers while satisfying the given conditions. We can sort the workers based on their wage/quality ratio. Then, for each worker, we calculate the cost of hiring that worker and k-1 other workers with the minimum wage/quality ratio. This allows us to find the minimum cost while ensuring that each worker is paid according to their quality.

Algorithm

Calculate the wage/quality ratio for each worker and sort the workers based on this ratio in ascending order.
Initialize variables to keep track of the minimum cost.
Iterate through the workers sorted by the wage/quality ratio.
For each worker, calculate the cost of hiring that worker and k-1 other workers with the minimum wage/quality ratio.
Update the minimum cost if the current cost is less than the minimum cost.
Return the minimum cost as the result.

Time Complexity

The time complexity of this algorithm is O(n log n) where n is the number of workers. This is due to the sorting operation.

Space Complexity

The space complexity is O(n) to store the sorted workers.

Solution Code

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

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));

        double minCost = Double.MAX_VALUE;
        int sumQuality = 0;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

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

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

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

        return minCost;
    }

    class Worker {
        int quality;
        int wage;
        double ratio;

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 857 (Minimum Cost to Hire K Workers)?

This page provides optimized solutions for LeetCode problem 857 (Minimum Cost to Hire K Workers) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 857 (Minimum Cost to Hire K Workers)?

The time complexity for LeetCode 857 (Minimum Cost to Hire K Workers) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 857 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 857 in Java, C++, or Python.

Back to LeetCode Solutions