LeetCode – Costo mínimo para contratar trabajadores K (Java)

Hay N trabajadores. El i-ésimo trabajador tiene una cualidad[i] y un salario mínimo de expectativa de salario[i].

Ahora queremos contratar exactamente K trabajadores para formar un grupo remunerado. Al contratar un grupo de trabajadores K, debemos pagarles de acuerdo con las siguientes reglas:
A cada trabajador del grupo remunerado se le debe pagar en la proporción de su calidad en comparación con otros trabajadores del grupo remunerado.
A cada trabajador del grupo remunerado se le debe pagar al menos su salario mínimo esperado.
Devuelva la menor cantidad de dinero necesaria para formar un grupo pagado que satisfaga las condiciones anteriores.

Ejemplo:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

Solución Java

Primero, clasifique a los trabajadores por su relación salario / calidad en orden ascendente. El valor de la relación más pequeño significa mejor calidad y bajos salarios. Luego, pruebe primero la mejor proporción y use el montón para rastrear la calidad más grande. Dada una proporción, la calidad más grande se elimina de la cola porque requiere más salario.

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        ArrayList<Worker> list = new ArrayList<>();
        for(int i=0; i<wage.length; i++){
            list.add(new Worker(quality[i], wage[i]));
        }
        Comparator<Worker> comp = Comparator.comparing((Worker w) -> w.ratio);
        Collections.sort(list, comp);
 
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int sum = 0;
        double result = Integer.MAX_VALUE;
 
        for(int i=0; i<list.size(); i++){
            Worker w = list.get(i);
            sum += w.quality;
            q.offer(-w.quality);
 
            if(q.size()>K){
                int extra = q.poll();
                sum += extra;
            }
 
            if(q.size() == K){
                result = Math.min(result, sum * w.ratio);        
            }
        }
 
        return result;
    }
}
 
class Worker{
    int quality;
    int wage;
    double ratio;
 
    public Worker(int q, int w){
        this.quality = q;
        this.wage = w;
        this.ratio = (double)w/q;
    }
}