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


回到顶部