LC-0857 Hard LeetCode

857. Minimum Cost to Hire K Workers

Array Greedy Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 63% Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:   O(nlogn)
# Space : O(n)

import itertools
import heapq


class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        """
        :type quality: List[int]
        :type wage: List[int]
        :type K: int
        :rtype: float
        """
        result, qsum = float("inf"), 0
        max_heap = []
        for r, q in sorted([float(w)/q, q] for w, q in itertools.izip(wage, quality)):
            qsum += q
            heapq.heappush(max_heap, -q)
            if len(max_heap) > K:
                qsum -= -heapq.heappop(max_heap)
            if len(max_heap) == K:
                result = min(result, qsum*r)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT