Maximum Performance of a Team

How it works

The key insight is that the minimum efficiency in a team acts as a bottleneck. If we fix which engineer has the minimum efficiency, we want to maximize the sum of speeds among the remaining selected engineers.

By sorting engineers in descending order of efficiency, as we iterate through them, each new engineer we consider has the smallest efficiency so far. At that point, we want to pick the engineers with the highest speeds (up to k total) from those we have seen. A min-heap helps us efficiently maintain the top k speeds.

Steps

1. Pair each engineer's efficiency with their speed and sort by efficiency in descending order.
2. Use a min-heap to track the speeds of selected engineers.
3. Iterate through the sorted list. For each engineer:
   • If the heap already has k engineers, remove the one with the smallest speed.
   • Add the current engineer's speed to the heap and update the speed sum.
   • Calculate performance using the current efficiency (which is now the minimum) and update the result.
4. Return the maximum performance modulo 10^9 + 7.

Complexity

• Time complexity: O(n * (log n + log k))
• Space complexity: O(n + k)

Where n is the number of engineers and k is the maximum number of engineers that can be selected.

Things to watch for

Integer Overflow When Computing Performance

The performance value is (sum of speeds) * (minimum efficiency), which can exceed the 32-bit integer range for large inputs. Use 64-bit integers (long in Java, long long in C++) for intermediate calculations, and only apply the modulo when returning the final result.

Applying Modulo During Computation Instead of at the End

The modulo operation should only be applied to the final answer, not during intermediate maximum comparisons. Applying modulo too early (e.g., res = max(res, performance % MOD)) corrupts the comparison logic because a smaller modulo result might incorrectly appear larger than the true maximum.

Misunderstanding "At Most k Engineers"

The problem asks for at most k engineers, meaning teams of size 1, 2, ..., up to k are all valid. A common mistake is only considering teams of exactly size k. The heap-based solution naturally handles this by computing performance at each step as engineers are added.

Incorrect Heap Management

When the heap exceeds k engineers, you must remove the engineer with the smallest speed (the top of a min-heap). A common error is using a max-heap instead, which would remove the fastest engineer and yield suboptimal results. The min-heap ensures we always keep the k fastest engineers seen so far.

Forgetting to Update Speed Sum When Popping from Heap

After removing an engineer from the heap, the speed sum must be decremented by that engineer's speed. Forgetting this update causes the speed sum to be incorrectly inflated, leading to wrong performance calculations.

from typing import List
import heapq

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        MOD = 10**9 + 7
        eng = sorted(zip(efficiency, speed), reverse=True)

        res = speedSum = 0
        minHeap = []

        for eff, spd in eng:
            if len(minHeap) == k:
                speedSum -= heapq.heappop(minHeap)
            speedSum += spd
            heapq.heappush(minHeap, spd)
            res = max(res, eff * speedSum)

        return res % MOD

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        constexpr int MOD = 1'000'000'007;
        vector<pair<int, int>> engineers;

        for (int i = 0; i < n; i++) {
            engineers.emplace_back(efficiency[i], speed[i]);
        }

        sort(engineers.rbegin(), engineers.rend());

        priority_queue<int, vector<int>, greater<int>> minHeap;
        long long speedSum = 0, res = 0;

        for (const auto& [eff, spd] : engineers) {
            if (minHeap.size() == k) {
                speedSum -= minHeap.top();
                minHeap.pop();
            }
            speedSum += spd;
            minHeap.push(spd);
            res = max(res, speedSum * eff);
        }

        return res % MOD;
    }
};