NeetCode #550LC-1383HardHeap / Priority Queue
← Back to All Problems#550 · #1383 · Maximum Performance of a Team(最大的团队表现值)
📌 Problem Statement & Constraints
You are given
n engineers with speed[i] and efficiency[i]. Choose at most k engineers to maximise (sum of speeds) * (minimum efficiency in the team). Return the answer modulo 10^9 + 7. Constraints: 1 <= n <= 10^5, 1 <= k <= n, 1 <= speed[i], efficiency[i] <= 10^8.💡 Core Algorithmic Approaches
- Sort by efficiency descending, so the current engineer has the minimum efficiency of those considered.
- Maintain a min-heap of the
klargest speeds seen so far, plus their sum. - For each engineer, the candidate score is
sum * efficiency. - The heap cap keeps the sum maximal for the current minimum efficiency.
💻 Benchmark Python3 Implementation
class Solution:
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
import heapq
MOD = 10 ** 9 + 7
pairs = sorted(zip(efficiency, speed), reverse=True) # efficiency desc
h = [] # the k largest speeds so far
total = 0
best = 0
for eff, sp in pairs:
heapq.heappush(h, sp)
total += sp
if len(h) > k:
total -= heapq.heappop(h) # evict the slowest
best = max(best, total * eff) # eff is the minimum so far
return best % MOD⚡ 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
- Sorting by speed: the minimum efficiency drives the ordering.
- Taking the modulo before the maximum: the comparison must use the true values; only the final answer is reduced.
- Keeping a max-heap of speeds: the smallest must be evicted, so a min-heap is needed.
- Requiring exactly
kengineers: any team size up tokis allowed, so the best is updated at every step.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.