Задача: 857. Minimum Cost to Hire K Workers
Сложность: hard

Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника.

Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами:

Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение.
В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше.
Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты.

Пример:

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

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

class Solution {
    func mincostToHireWorkers(_ quality: [Int], _ wage: [Int], _ k: Int) -> Double {
        let n = quality.count
        var totalCost = Double.greatestFiniteMagnitude
        var currentTotalQuality = 0.0
        var wageToQualityRatio = [(Double, Int)]()

        for i in 0..<n {
            wageToQualityRatio.append((Double(wage[i]) / Double(quality[i]), quality[i]))
        }

        wageToQualityRatio.sort { $0.0 < $1.0 }
        var workers = PriorityQueue<Int>(sort: >)

        for ratio in wageToQualityRatio {
            workers.enqueue(ratio.1)
            currentTotalQuality += Double(ratio.1)

            if workers.count > k {
                currentTotalQuality -= Double(workers.dequeue()!)
            }

            if workers.count == k {
                totalCost = min(totalCost, currentTotalQuality * ratio.0)
            }
        }
        return totalCost
    }
}

struct PriorityQueue<Element: Comparable> {
    private var elements: [Element] = []
    private let sort: (Element, Element) -> Bool

    init(sort: @escaping (Element, Element) -> Bool) {
        self.sort = sort
    }

    var count: Int {
        return elements.count
    }

    mutating func enqueue(_ element: Element) {
        elements.append(element)
        elements.sort(by: sort)
    }

    mutating func dequeue() -> Element? {
        return elements.isEmpty ? nil : elements.removeFirst()
    }
}

Ставь 👍 и забирай 📚 Базу знаний