Minimum Cost to Hire K Workers

Max Heap

Hard

There areNworkers. Thei-th worker has aquality[i]and a minimum wage expectationwage[i].

Now we want to hire exactlyK workers to form apaid group. When hiring a group of K workers, we must pay them according to the following rules:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.

2. Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

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

Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667

Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately.

Note:

1. 1 <= K <= N <= 10000, where N = quality.length = wage.length

2. 1 <= quality[i] <= 10000

3. 1 <= wage[i] <= 10000

4. Answers within 10^-5 of the correct answer will be considered correct.

Solution & Analysis

关键在于想到

1.把 wage / quality作为排序的标准，这样从小到大排序，也就代表了性价比从高到低，优先选择性价比高的

1. 在选择一个 wage/quality的比率之后，决定最终cost就是总的quality了，因此用一个max-heap来存入所选取的worker的quality值，如果超出k个，则从max-heap中poll()，这时去掉的就是quality值在当前最高的

复杂度分析：

• Time Complexity: O(NlogN), where N is the number of workers. 先排序 O(NlogN), 外层循环 O(N)，内层Heap操作O(logK)

• Space Complexity:O(N).

33 ms, faster than 83.03%

class Solution {
    class Worker implements Comparable<Worker> {
        int wage;
        int quality;
        public Worker(int q, int w) {
            quality = q;
            wage = w;
        }
        public double ratio() {
            return (double) wage / quality;
        }

        @Override
        public int compareTo(Worker other) {
            return Double.compare(ratio(), other.ratio());
        }
    }

    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);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int sumOfQuality = 0;
        double ans = Double.MAX_VALUE;
        for (Worker worker: workers) {
            double ratio = worker.ratio();
            maxHeap.offer(worker.quality);
            sumOfQuality += worker.quality;
            if (maxHeap.size() > K) {
                sumOfQuality -= maxHeap.poll();
            }
            if (maxHeap.size() == K) {
                ans = Math.min(ans, ratio * sumOfQuality);
            }
        }
        return ans;
    }
}

简化写法LeetCode Solution:

存入的-worker.quality,这样正巧满足了min-heap时，堆顶其实是绝对值最大，建heap时也不用pass一个Collections.reverseOrder()到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);

        double ans = 1e9;
        int sumq = 0;
        PriorityQueue<Integer> pool = new PriorityQueue();
        for (Worker worker: workers) {
            pool.offer(-worker.quality);
            sumq += worker.quality;
            if (pool.size() > K)
                sumq += pool.poll();
            if (pool.size() == K)
                ans = Math.min(ans, sumq * worker.ratio());
        }

        return ans;
    }
}

class Worker implements Comparable<Worker> {
    public int quality, wage;
    public Worker(int q, int w) {
        quality = q;
        wage = w;
    }

    public double ratio() {
        return (double) wage / quality;
    }

    public int compareTo(Worker other) {
        return Double.compare(ratio(), other.ratio());
    }
}

Reference

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/141768/Detailed-explanation-O(NlogN\)

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/solution/