How hard is LeetCode 857. Minimum Cost to Hire K Workers?

LeetCode 857. Minimum Cost to Hire K Workers is rated Hard on LeetCode.

What topics does LeetCode 857. Minimum Cost to Hire K Workers cover?

LeetCode 857. Minimum Cost to Hire K Workers is tagged Greedy, Array, Sorting and Heap (Priority Queue) on LeetCode.

Minimum Cost to Hire K Workers — LeetCode 857 Python Solution

HardGreedyArraySortingHeap (Priority Queue)

Problem: #857
Pattern: Heap / Priority Queue
Reading time: 3 min
Source: leetcode.com

The problem

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

Example

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.

Python solution

Python

class Solution:
    def mincostToHireWorkers(
        self, quality: List[int], wage: List[int], k: int
    ) -> float:
        t = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])
        ans, tot = inf, 0
        h = []
        for q, w in t:
            tot += q
            heappush(h, -q)
            if len(h) == k:
                ans = min(ans, w / q * tot)
                tot += heappop(h)
        return ans

Complexity

Measure	Complexity
Time	O(n log n)
Space	O(1) to O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 857. Minimum Cost to Hire K Workers is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 857. Minimum Cost to Hire K Workers?: LeetCode 857. Minimum Cost to Hire K Workers is rated Hard on LeetCode.
What topics does LeetCode 857. Minimum Cost to Hire K Workers cover?: LeetCode 857. Minimum Cost to Hire K Workers is tagged Greedy, Array, Sorting and Heap (Priority Queue) on LeetCode.