⚡Flashcard Drill➔
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

  1. For a chosen team, the pay rate must be max(wage[i] / quality[i]) over the team, so the cost is rate * sum(quality).
  2. Sort the workers by their wage / quality ratio ascending; the current worker supplies the binding rate.
  3. Maintain a max-heap of the k smallest qualities seen so far, plus their sum -- minimising the sum for a fixed rate.
  4. The answer is the minimum of rate * quality_sum over 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 ratio wage[i] / quality[i]: the binding constraint is the pay per unit of quality.
  • Keeping the k largest qualities: the sum must be minimised, so the smallest qualities are kept.
  • Forgetting the len(h) == k guard: a team smaller than k is 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems