Minimum Cost to Hire K Workers

Problem

Minimum Cost to Hire K Workers

Intuition

1. Firstly, we have to get the ratio, which is the average wage per quality, of all workers.
2. With the ratio, we can know that who is the most efficient worker. If these ratio are sorted in ascending order, so we can get current max ratio in some index.
3. Then, totalAmountMoney = max_ratio * the_K_worker_quality. As for some K workers, we have to make sure the the_K_worker_quality is smallest, where max_heap can work very well.

Code

class Solution {
    class Worker{
        int q, w;
        double r;
        public Worker(int q, int w){
            this.q = q;
            this.w = w;
            r = (double)w/q;
        }
    }
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        List<Worker> ws = new ArrayList<>();
        for(int i = 0; i < quality.length; i ++){
            Worker temp = new Worker(quality[i], wage[i]);
            ws.add(temp);
        }
        Collections.sort(ws, new Comparator<Worker>(){
            @Override
            public int compare(Worker a, Worker b){
                if(a.r < b.r) return -1;
                if(a.r == b.r) return 0;
                return 1;
            }
        });
        double ans = Double.MAX_VALUE;
        int qSum = 0;
        PriorityQueue<Worker> pq = new PriorityQueue<>(new Comparator<Worker>(){
            @Override
            public int compare(Worker a, Worker b){
                return - a.q + b.q;
            }
        });
        // sorted ws works for the iteration
        for(int i = 0; i < ws.size(); i ++){
            qSum += ws.get(i).q;
            pq.add(ws.get(i));
            if(pq.size() > K){
                qSum -= pq.poll().q;
            }
            if(pq.size() == K){
                ans = Math.min(ans, ws.get(i).r * qSum);
            }
        }
        return ans;
    }
}