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

  1. Sort by efficiency descending, so the current engineer has the minimum efficiency of those considered.
  2. Maintain a min-heap of the k largest speeds seen so far, plus their sum.
  3. For each engineer, the candidate score is sum * efficiency.
  4. 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 k engineers: any team size up to k is 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems