[LeetCode] 857. Minimum Cost to Hire K Workers

solocoder 发布于2019-08-16 13:54 / 1302人阅读

Problem

There are N workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i].

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

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
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 <= K <= N <= 10000, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
Answers within 10^-5 of the correct answer will be considered correct.

Solution

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        int n = quality.length;
        double[][] workers = new double[n][2];
        for (int i = 0; i < n; i++) {
            double ratio = (double) wage[i] / quality[i];
            workers[i] = new double[]{ratio, (double) quality[i]};
        }
        
        Arrays.sort(workers, (a, b)->Double.compare(a[0], b[0]));
        PriorityQueue pq = new PriorityQueue<>((a, b)->Double.compare(b, a));
        
        double total = Double.MAX_VALUE, temp = 0;
        for (double[] worker: workers) {
            temp += worker[1];
            pq.offer(worker[1]);
            if (pq.size() > K) {
                double maxQuality = pq.poll();
                temp -= maxQuality;
            }
            if (pq.size() == K) {
                double curTotal = temp*worker[0];
                total = Math.min(total, curTotal);
            }
        }
        
        return total;
    }
}

GPU云服务器云服务器 Hire Cost Minimum Workers

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72540.html

[Leetcode] Paint House 房子涂色

摘要：动态规划复杂度时间空间思路直到房子，其最小的涂色开销是直到房子的最小涂色开销，加上房子本身的涂色开销。我们在原数组上修改，可以做到不用空间。代码找出最小和次小的，最小的要记录下标，方便下一轮判断 Paint House There are a row of n houses, each house can be painted with one of the three colors...

SunZhaopeng 2019-08-14 12:46 评论0 收藏0
265. Paint House II

摘要：题目解答利用的思路，只不过把三种颜色换成了种颜色，所以是如何把它的复杂度降到那么就是如果将颜色的部分只扫一遍。参考的里只需要记录下每个的最小的两个颜色。题目：There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house w...

mylxsw 2019-08-14 14:08 评论0 收藏0
leetcode 746 Min Cost Climbing Stairs

摘要：同时你可以选择从第阶开始或者第一阶开始。我们的目标是找出你爬到最顶层所付出的最小的开销。最低开销是，从第阶开始，只花费就可以到顶层。想法动态规划问题。的长度应该为数组长度加一，其中数组的最后一个元素的值就是本题的答案，最低开销。题目详情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...

fyber 2019-08-16 11:01 评论0 收藏0
[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原数组上动规，每一行对应一个房子，每一个元素代表从第一行的房子到这一行的房子选择这一种颜色所花的最小开销。所以每个元素该元素的值上一行两个与该元素不同列元素的值的较小者。不过这次要记录三个变量本行最小值，本行第二小值，本行最小值下标。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 评论0 收藏0