AlgoMaster Logo

Maximum Performance of a Team

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We need to pick at most k engineers to maximize sum(speed) * min(efficiency). The two factors pull against each other. Adding more engineers raises the speed sum, but it can lower the minimum efficiency. So the optimal team is not always the one with the highest total speed, nor the one with the highest minimum efficiency.

The way to untangle this is to fix which engineer has the minimum efficiency. Once the minimum efficiency is some value e, the only engineers worth picking are those whose efficiency is at least e. Any engineer with efficiency below e would become the new minimum and break the assumption. Among the eligible engineers, we want the highest speeds, because that maximizes the speed sum without lowering the minimum.

Fixing one dimension and optimizing the other turns an exponential search into a single pass.

Key Constraints:

  • 1 <= n <= 10^5. With up to 100,000 engineers, the solution must run in O(n log n) or better. An O(n^2) or O(n * k) approach with large k is too slow.
  • 1 <= efficiency[i] <= 10^8 and 1 <= speed[i] <= 10^5. The product sum(speed) * min(efficiency) reaches up to 10^5 10^5 10^8 = 10^18, which overflows a 32-bit int. The intermediate arithmetic must use 64-bit long, and only the final answer is reduced modulo 10^9 + 7.
  • 1 <= k <= n. "At most k" means a team of fewer than k engineers can win, so the answer must also consider smaller teams.

Approach 1: Brute Force (Enumerate All Teams)

Intuition

Try every possible team of size 1 to k and compute its performance. For each subset, sum the speeds, find the minimum efficiency, and multiply. Track the maximum across all subsets.

This is correct but the number of subsets grows combinatorially, so it is only practical when n is small.

Algorithm

  1. Generate all subsets of engineers with size between 1 and k.
  2. For each subset, compute sum(speed) * min(efficiency).
  3. Return the maximum performance across all subsets, modulo 10^9 + 7.

Visualization and Code

Loading animation...

This approach is exponential. Fixing the minimum efficiency, as described earlier, removes the need to enumerate subsets at all.

Approach 2: Sort by Efficiency + Min-Heap (Greedy)

Intuition

Instead of enumerating subsets, fix the minimum efficiency and optimize the speed sum around it.

Sort all engineers by efficiency in decreasing order and process them left to right. When we reach engineer i, its efficiency is the smallest among all engineers seen so far. So if we build a team from engineer i plus any subset of the engineers already processed (indices 0 through i-1), engineer i is the one contributing the minimum efficiency.

The remaining question is which of the engineers processed so far, including engineer i, to include so the speed sum is largest. We want the top-k speeds. A min-heap capped at size k maintains exactly that: push each engineer's speed, and when the heap exceeds k elements, pop the smallest speed. At each step, the best team whose minimum efficiency is the current engineer's efficiency has performance speedSum * currentEfficiency, and we track the maximum over all steps.

Algorithm

  1. Pair each engineer's speed and efficiency together, then sort these pairs by efficiency in decreasing order.
  2. Initialize a min-heap (priority queue) for speeds, a running speedSum = 0, and maxPerf = 0.
  3. For each engineer in the sorted order:
    • Add their speed to the heap and add it to speedSum.
    • If the heap size exceeds k, pop the smallest speed and subtract it from speedSum.
    • Compute performance = speedSum * currentEfficiency.
    • Update maxPerf = max(maxPerf, performance).
  4. Return maxPerf % (10^9 + 7).

Visualization and Code

Loading animation...