1383 - Maximum Performance of a Team

Difficulty: Hard | Pattern: Greedy + Min-Heap | Company tags: Amazon, Google

Problem Statement

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. engineer[i] has speed speed[i] and efficiency efficiency[i].

Choose at most k engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of speeds of all engineers times the minimum efficiency among all engineers in the team: perf = sum(speeds) × min(efficiency).

Return the maximum performance of this team, modulo 10^9 + 7.

Example 1:

Input: n=6, speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=2
Output: 56
Explanation: [10,5] team: sum_speed=15, min_eff=4 → 60? Or [10,3] with eff=[4,3]: 13×3=39
Actually: engineer 2 (speed=10, eff=4), engineer 5 (speed=5, eff=7): min_eff=4, sum=15 → 60? 
Best: engineer 2 (10, eff=4) + engineer 4 (1, eff=9) → sum=11, min_eff=4 → 44
Or just engineer 4 alone: 1×9=9. Let me check [10,5,7] team...

Approach: Sort by Efficiency (Descending) + Min-Heap — O(n log n)

Key insight: Sort engineers by efficiency descending. For each engineer i, treat their efficiency as the minimum (since all selected engineers have higher efficiency). Greedily pick the top-k speeds from already-seen engineers using a min-heap.

import heapq

def maxPerformance(n: int, speed: list[int], efficiency: list[int], k: int) -> int:
    MOD = 10**9 + 7
    
    # Sort by efficiency descending
    engineers = sorted(zip(efficiency, speed), reverse=True)
    
    heap = []  # min-heap of speeds
    speed_sum = 0
    best = 0
    
    for eff, spd in engineers:
        heapq.heappush(heap, spd)
        speed_sum += spd
        
        if len(heap) > k:
            speed_sum -= heapq.heappop(heap)  # remove slowest
        
        best = max(best, speed_sum * eff)
    
    return best % MOD

Algorithm Flow

Why This Works

By sorting efficiency descending, when we process engineer i, their efficiency is the minimum for any team that includes them AND was formed only from engineers processed so far. We maximize sum(speed) subject to choosing at most k engineers.

Dry Run

speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=2

Sorted by eff desc: [(9,1),(7,5),(5,2),(4,10),(3,3),(2,8)]

eff	spd	heap	speed_sum	perf
9	1	[1]	1	1×9=9
7	5	[1,5]	6	6×7=42
5	2	[1,2,5] → pop 1	7	7×5=35
4	10	[2,5,10] → pop 2	15	15×4=60
3	3	[3,5,10] → pop 3	15	15×3=45
2	8	[5,8,10] → pop 5	18	18×2=36

best = 60 ✓ (confirmed: 10×4=40 plus 5×4=20 = 60, min_eff=4)

Complexity

• Time: O(n log n) for sort + O(n log k) for heap operations
• Space: O(k) for heap

Common Mistakes

• Sorting by speed instead of efficiency — the min-heap trick only works because sorting by efficiency descending guarantees the current engineer's efficiency is the minimum for the team built so far.
• Forgetting to pop from the heap before (or without) updating best when heap size exceeds k, which lets a team of more than k engineers count toward the answer.
• Applying the modulo inside the running speed_sum or during heap comparisons — this corrupts comparisons and sums; only take % MOD on the final returned value.
• Using a max-heap on speed instead of a min-heap — you need to evict the smallest speed to keep the largest sum of the best k speeds.

Edge Cases

• k == 1: performance reduces to max(speed[i] * efficiency[i]) for any single engineer.
• k >= n: every engineer can be included; the heap never needs to evict, so the answer is the max over all prefixes of the full speed sum times current efficiency.
• All efficiencies equal: the answer is simply the sum of the top k speeds times that shared efficiency.
• Duplicate (speed, efficiency) pairs: handled naturally since the heap only tracks speed values, ties in efficiency don't affect correctness of the sort-then-heap approach.

Variants

• Task Scheduling with deadlines and profits — similar greedy + heap pattern where you process by one sorted key and maintain a heap for the other.
• IPO / Maximize Capital (LeetCode 502) — greedy selection bounded by a budget, using a heap to pick the best available option at each step.
• Meeting Scheduler style interval problems — see 1229-MeetingScheduler.md for a related greedy + heap/sort pattern.

Key Terms

Term	Definition
Min-heap	A priority queue that always exposes the smallest element in O(1), with O(log n) insert/remove — used here to track the smallest speed in the current window of k engineers.
Greedy by sorted key	Processing elements in a fixed sort order (efficiency descending) so that each element, once visited, can safely be treated as the limiting factor (minimum efficiency) for all elements considered before it.
Sliding window of size k (via heap)	Maintaining exactly the top-k speeds seen so far by evicting the smallest whenever the heap grows past size k.
Running aggregate	Tracking speed_sum incrementally instead of recomputing it from the heap each iteration, keeping each step O(log k) instead of O(k).

FAQ

Q: Can this be solved without a heap? A: Yes, with O(n^2) brute force (for each engineer as the minimum-efficiency anchor, scan all higher-efficiency engineers and pick top-k speeds by sorting each time), but that's O(n^2 log n) at best — the heap approach is required for O(n log n) at scale.

Q: What if speed and efficiency arrays have different lengths or n is 0? A: The problem guarantees both arrays have length n; if n == 0 there are no engineers, so the answer is 0 (the loop never executes and best stays at its initial value).

Q: Why sort by efficiency descending and not speed descending? A: Efficiency is the term being minimized in the performance formula. Sorting by efficiency descending lets each engineer processed represent the minimum efficiency of the team formed from all engineers seen so far, which speed doesn't do since speed is summed, not minimized.

Q: How would the approach change if we wanted the minimum performance instead of maximum? A: The problem would become nearly trivial/degenerate (pick the engineer with the single lowest speed and lowest efficiency), since minimizing sum(speed) * min(efficiency) with at least one engineer just means picking the weakest single engineer — the heap machinery is only needed for maximization under the "top-k speeds" constraint.

Q: Does the order of ties in efficiency matter? A: No — when two engineers have equal efficiency, either sort order works because at the moment of a tie, both are eligible to be in the heap simultaneously and the min-heap eviction logic doesn't depend on efficiency order, only on speed values.

Quick Revision

• Performance = sum(speed of team) × min(efficiency of team); choose at most k engineers to maximize it.
• Sort engineers by efficiency descending so each engineer, when processed, can serve as the team's minimum efficiency.
• Maintain a min-heap of speeds capped at size k; push current engineer's speed, track running speed_sum.
• If heap exceeds size k, pop the smallest speed and subtract it from speed_sum — this keeps only the top-k speeds seen so far.
• After each push/pop, update best = max(best, speed_sum * current_efficiency).
• Time complexity: O(n log n) for sort + O(n log k) for heap ops; space: O(k) for the heap.
• Take % (10^9 + 7) only on the final returned answer, never mid-computation.
• Pattern generalizes: "process by one sorted dimension while maintaining a heap-bounded aggregate on the other dimension."