857. Minimum Cost to Hire K Workers

//  wage / quality -> min ratio a worker needs to be paid
        // if r > wage[i] / quality[i] -> worker i can be satisfied
        // we have to pay the maximum  r = wage[i] / quality[i] among the group to satisfy all workers
        // total = max(wage[i] / quality[i]) * sum(quality)
        // we want to minimize the sum of quality and ratio

Time O(NlogN)
如果用 Double[] 代替Worker class应该会更快
注意两个写法
-> PQ在new的时候不能infer<> type
PriorityQueue<Worker> que = new PriorityQueue<Worker>(
            (a, b) -> {
                return b.ratio.compareTo(a.ratio);
            }
        );

-> a, b 要声明type
Collections.sort(workers, (Worker a, Worker b) -> a.qua.compareTo(b.qua));

47.54 %
class Solution {
    class Worker {
        Integer qua;
        Double ratio;
        public Worker(int qua, int wage) {
            this.qua = qua;
            this.ratio = 1.0 * wage / qua;
        }
    }
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        List<Worker> workers = new ArrayList<>();
        for (int i = 0; i < quality.length; i++) {
            workers.add(new Worker(quality[i], wage[i]));
        }
        Collections.sort(workers, (Worker a, Worker b) -> a.qua.compareTo(b.qua));
        int sum = 0;
        // index
        PriorityQueue<Worker> que = new PriorityQueue<Worker>(
            (a, b) -> {
                return b.ratio.compareTo(a.ratio);
            }
        );
        double min = Integer.MAX_VALUE;
     
        for (int i = 0; i < workers.size(); i++) {
            if (que.size() >= K) {
                sum -= que.poll().qua;
            }
         
            sum += workers.get(i).qua;
            que.offer(workers.get(i));
            if (que.size() >= K) {
                min = Math.min(min, sum * que.peek().ratio);
            }
        }
        return min;
    }
}