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 and refine your code.

LeetCode 857: Minimum Cost to Hire K Workers Solution

Problem Description

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.

Solutions

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