NeetCode #552LC-857HardHeap / Priority Queue
← Back to All Problems#552 · #857 · Minimum Cost to Hire K Workers(雇佣 K 名工人的最低成本)
📌 Problem Statement & Constraints
There are
n workers with quality[i] and a minimum expected wage wage[i]. Hire exactly k workers and pay each the same amount per unit of quality, at least their expectation. Return the minimum total cost. Constraints: 1 <= k <= n <= 10^4, 1 <= quality[i] <= 10^4, 1 <= wage[i] <= 10^4.💡 Core Algorithmic Approaches
- For a chosen team, the pay rate must be
max(wage[i] / quality[i])over the team, so the cost israte * sum(quality). - Sort the workers by their
wage / qualityratio ascending; the current worker supplies the binding rate. - Maintain a max-heap of the
ksmallest qualities seen so far, plus their sum -- minimising the sum for a fixed rate. - The answer is the minimum of
rate * quality_sumover all valid prefixes.
💻 Benchmark Python3 Implementation
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
import heapq
workers = sorted((w / q, q) for q, w in zip(quality, wage))
h = [] # max-heap of qualities (negated)
total_q = 0
best = float("inf")
for ratio, q in workers:
heapq.heappush(h, -q)
total_q += q
if len(h) > k:
total_q += heapq.heappop(h) # the popped value is negative
if len(h) == k:
best = min(best, ratio * total_q)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort plus O(n) heap operations.
💾 Space Complexity
O(k) for the heap.
⚠️ Interview Pitfalls & Follow-ups
- Using
wage[i]instead of the ratiowage[i] / quality[i]: the binding constraint is the pay per unit of quality. - Keeping the
klargest qualities: the sum must be minimised, so the smallest qualities are kept. - Forgetting the
len(h) == kguard: a team smaller thankis invalid. - Using a min-heap: the largest quality must be evicted to minimise the sum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.