Leetcode 887 Solution

This article provides solution to leetcode question 887 (minimum-cost-to-hire-k-workers)
Categories:
Tags:
Access this page by simply typing in "lcs 887" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/minimum-cost-to-hire-k-workers

Solution

class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        """
        :type quality: List[int]
        :type wage: List[int]
        :type K: int
        :rtype: float
        """
        a = sorted([(w * 1.0 / q, w, q) for w, q in zip(wage, quality)])



        heap = []
        heap_sum = 0
        ans = sys.maxint



        for r, w, q in a:
            heapq.heappush(heap, -q)
            heap_sum += q



            if len(heap) == K:
                ans = min(ans, heap_sum * r)
                heap_sum += heapq.heappop(heap)



        return ans