LC857. Minimum Cost to Hire K Workers

Approach 1: Max Heap

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        res = float("inf")
 
        costPerQualityList = [
            (w / q, q) for (w, q) in zip(wage, quality)
        ]
        costPerQualityList.sort()
 
        maxHeap = []
        totalQuality = 0
 
        for costPerQuality, q in costPerQualityList:
            # There is no max heap in py, only min heap. So we negate
            # before pushing which gives an equivalent. Just need to remember
            # that the pushed value has the opposite sign.
            heapq.heappush(maxHeap, -q)
            totalQuality += q
 
            if len(maxHeap) > k:
                maxQuality = heapq.heappop(maxHeap)
                totalQuality += maxQuality     # We negated the val already, hence +=
 
            if len(maxHeap) == k:
                res = min(
                    res,
                    totalQuality * costPerQuality # costPerQuality will be the highest since
                )                                 # list is sorted in ascending order and dictates
                                                  # total cost
 
        return res

Complexity

Time: $O(nlog(n+k))$
Space: $O(n)$

Notes

In a group of workers, the highest rate (i.e wage / quality) of a member defines the rate for all the members based on problem description. We can’t pay different wages to different workers as the wage must be proportional to quality.

Other Languages