857. Minimum Cost to Hire K Workers - Explanation

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        pairs = sorted([(w / q, q) for q, w in zip(quality, wage)], key=lambda p: p[0])

        maxHeap = []
        total_quality = 0
        res = float("inf")

        for rate, q in pairs:
            heapq.heappush(maxHeap, -q)
            total_quality += q

            if len(maxHeap) > k:
                total_quality += heapq.heappop(maxHeap)

            if len(maxHeap) == k:
                res = min(res, total_quality * rate)

        return res