Skip to content

857. Minimum Cost to Hire K Workers

857. Minimum Cost to Hire K Workers

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

难度: Hard

题意：

  1. n个工人，有一个工作量数组quality，有个最低工资数组wage
  2. 要聘用K个工人，工资最低。要求，这n个工人的工资必须不低于他们的最低工资要求，并且他们的工资跟工作量成正比

思路：

  • 由于工资跟工作量成正比，假设这个比率是r。第i工人愿意被聘用的条件是r>=wage[i]/quality[i]
  • 令ratio[i]=wage[i]/quality[i]，对ratio[i]排序，遍历数组ratio，i每递曾一个，就有一个工人愿意被聘用
  • 假设现在有p个工人愿意被聘用(p>=K)，现在轮到我们来挑选K个人，由于工资总和要最低，且工资=工作量*p，所以在这p个人中挑选工作量最低的K个人
  • 子问题是，求数列中前K小的数，需要最小堆
  • 复杂度是o(nlogn)

代码：

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        double[] ratio = new double[quality.length];
        Integer[] pos = new Integer[quality.length];
        for (int i = 0;i < quality.length;i++) {
            ratio[i] = (double) wage[i] / quality[i];
            pos[i] = i;
        }
        Arrays.sort(pos, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Double.compare(ratio[o1], ratio[o2]);
            }
        });
        double ret = 1e40;
        int maxK = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });
        for (int i = 0;i < pos.length;i++) {
            maxK += quality[pos[i]];
            queue.add(quality[pos[i]]);
            if (queue.size() > K) {
                maxK -= queue.poll();
            }
            if (queue.size() == K) {
                ret = ret > maxK * ratio[pos[i]] ? maxK * ratio[pos[i]] : ret;
            }
        }
        return ret;
    }
}
回到顶部