857. Minimum Cost to Hire K Workers

public class Solution {
    public double MincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.Length;
        double totalCost = double.MaxValue;
        double currentTotalQuality = 0;
        var wageToQualityRatio = new List<(double, int)>();
        for (int i = 0; i < n; i++) {
            wageToQualityRatio.Add(((double) wage[i] / quality[i], quality[i]));
        }
        wageToQualityRatio.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        var workers = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        foreach (var (ratio, q) in wageToQualityRatio) {
            workers.Enqueue(q, q);
            currentTotalQuality += q;
            if (workers.Count > k) {
                currentTotalQuality -= workers.Dequeue();
            }
            if (workers.Count == k) {
                totalCost = Math.Min(totalCost, currentTotalQuality * ratio);
            }
        }
        return totalCost;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double MincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        double totalCost = double.MaxValue;
        double currentTotalQuality = 0;
        var wageToQualityRatio = new List<(double, int)>();
        for (int i = 0; i < n; i++) {
            wageToQualityRatio.push_back(((double) wage[i] / quality[i], quality[i]));
        }
        wageToQualityRatio.Sort((a, b) => a.Item1.CompareTo(b.Item1));
        var workers = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        foreach (var (ratio, q) in wageToQualityRatio) {
            workers.Enqueue(q, q);
            currentTotalQuality += q;
            if (workers.size() > k) {
                currentTotalQuality -= workers.Dequeue();
            }
            if (workers.size() == k) {
                totalCost = min(totalCost, currentTotalQuality * ratio);
            }
        }
        return totalCost;
    }
}

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double totalCost = Double.MAX_VALUE;
        double currentTotalQuality = 0;
        List<Pair<Double, Integer>> wageToQualityRatio = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            wageToQualityRatio.add(new Pair<>((double) wage[i] / quality[i], quality[i]));
        }

        wageToQualityRatio.sort(Comparator.comparingDouble(Pair::getKey));
        PriorityQueue<Integer> workers = new PriorityQueue<>(Collections.reverseOrder());

        for (Pair<Double, Integer> pair : wageToQualityRatio) {
            workers.add(pair.getValue());
            currentTotalQuality += pair.getValue();

            if (workers.size() > k) {
                currentTotalQuality -= workers.poll();
            }

            if (workers.size() == k) {
                totalCost = Math.min(totalCost, currentTotalQuality * pair.getKey());
            }
        }

        return totalCost;
    }
}

class Solution {
    mincostToHireWorkers(quality, wage, k) {
        const n = quality.length;
        let totalCost = Infinity;
        let currentTotalQuality = 0;
        const wageToQualityRatio = quality.map((q, i) => [wage[i] / q, q]).sort((a, b) => a[0] - b[0]);
        const workers = new MaxHeap();

        for (const [ratio, q] of wageToQualityRatio) {
            workers.push(q);
            currentTotalQuality += q;

            if (workers.size() > k) {
                currentTotalQuality -= workers.pop();
            }

            if (workers.size() === k) {
                totalCost = Math.min(totalCost, currentTotalQuality * ratio);
            }
        }
        return totalCost;
    }
}

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    push(val) {
        this.heap.push(val);
        this.heap.sort((a, b) => b - a);
    }

    pop() {
        return this.heap.shift();
    }
}

from heapq import heappop, heappush

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        n = len(quality)
        totalCost = float('inf')
        currentTotalQuality = 0
        wageToQualityRatio = [(w / q, q) for w, q in zip(wage, quality)]
        wageToQualityRatio.sort()
        workers = []

        for ratio, q in wageToQualityRatio:
            heappush(workers, -q)
            currentTotalQuality += q

            if len(workers) > k:
                currentTotalQuality += heappop(workers)

            if len(workers) == k:
                totalCost = min(totalCost, currentTotalQuality * ratio)

        return totalCost

Algorithm

Инициализируйте переменные: n для размера Arrayов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте Array wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию.

Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через sorted wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality.

Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. return totalCost.

😎