# 0857. Minimum Cost to Hire K Workers
###### tags: `Leetcode` `Hard` `Priority Queue`
Link: https://leetcode.com/problems/minimum-cost-to-hire-k-workers/
## 思路 $O(NlogN)$ $O(N)$
和[1383. Maximum Performance of a Team](https://hackmd.io/bKCHp-8yTLi42s5emUM0WQ)非常像
intuition可以参考那道题
思路参考[这里](https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/141768/Detailed-explanation-O(NlogN))已经非常详细了
## Code

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        double[][] workers = new double[quality.length][2];
        for(int i=0; i<quality.length; i++){
            workers[i] = new double[]{(double)wage[i]/quality[i], (double)quality[i]};
        }
        
        Arrays.sort(workers, (a,b)->Double.compare(a[0], b[0]));
        Queue<Double>pq = new PriorityQueue<>(Collections.reverseOrder());
        double money = Double.MAX_VALUE;
        double currQuality = 0;
        
        for(double[] worker:workers){
            if(pq.size()==k) currQuality -= pq.poll();
            pq.add(worker[1]);
            currQuality += worker[1];
            if(pq.size()==k)money = Math.min(money, currQuality*worker[0]);
        }
        return money;
    }
}