Maximum Performance of a Team — Hard Problem & Solution

Problem statement

There are n engineers, each with a speed and an efficiency. The performance of a team is the sum of its speeds multiplied by the minimum efficiency among its members.

Pick at most k engineers to maximise the performance, and return it 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: 60
Explanation: Engineers 1 and 4: `(10 + 5) × min(4, 7) = 15 × 4`.

Example 2

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68

Example 3

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints

• 1 <= k <= n <= 1000
• speed.length == efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^5

How to solve Maximum Performance of a Team

Sort by efficiency descending. At each step the current engineer fixes the team's minimum efficiency, so the best team ending there takes the k largest speeds among those seen — maintained by a size-k min-heap.

Approach

1. Sort the indices by efficiency, largest first.
2. Push each speed onto a min-heap and add it to a running sum.
3. If the heap exceeds k, pop the smallest speed and subtract it.
4. Score sum × efficiency[current] and keep the maximum; apply the modulus only at the end.

Why it works

The team may hold at most k engineers, so the score is taken at every step, not only once the heap is full — a smaller team with a very high minimum efficiency can win. Dropping the slowest engineer when the heap overflows is safe: they can never improve the sum for this or any later minimum.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Applying the modulus while comparing candidates picks the wrong maximum — reduce only at the end.
• Scoring only when the team is full misses the smaller high-efficiency teams.
• The products exceed a 32-bit int, so the running work needs a 64-bit accumulator.

Reference solution

Python

from typing import List
import heapq

def maxPerformance(n: int, speed: List[int], efficiency: List[int], k: int) -> int:
    MOD = 1000000007
    order = sorted(range(n), key=lambda i: -efficiency[i])
    heap = []
    total = 0
    best = 0
    for i in order:
        heapq.heappush(heap, speed[i])
        total += speed[i]
        if len(heap) > k:
            total -= heapq.heappop(heap)
        best = max(best, total * efficiency[i])
    return best % MOD

JavaScript

var maxPerformance = function(n, speed, efficiency, k) {
    var MOD = 1000000007, i;
    var order = [];
    for (i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return efficiency[b] - efficiency[a]; });
    var heap = [];
    var push = function(v) {
        heap.push(v);
        var j = heap.length - 1;
        while (j > 0) {
            var p = (j - 1) >> 1;
            if (heap[p] <= heap[j]) break;
            var t = heap[p]; heap[p] = heap[j]; heap[j] = t;
            j = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var j = 0;
            for (;;) {
                var l = 2 * j + 1, r = l + 1, s = j;
                if (l < heap.length && heap[l] < heap[s]) s = l;
                if (r < heap.length && heap[r] < heap[s]) s = r;
                if (s === j) break;
                var t = heap[s]; heap[s] = heap[j]; heap[j] = t;
                j = s;
            }
        }
        return top;
    };
    var sum = 0, best = 0;
    for (var t2 = 0; t2 < order.length; t2++) {
        var idx = order[t2];
        push(speed[idx]);
        sum += speed[idx];
        if (heap.length > k) sum -= pop();
        var perf = sum * efficiency[idx];
        if (perf > best) best = perf;
    }
    return best % MOD;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard