Maximum Performance of a Team
Problem
n engineers with speeds and efficiencies. Choose at most k of them to maximize (sum of their speeds) × (min of their efficiencies). Return the result mod 10^9+7.
n=6, speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=260import heapq
def max_performance(n, speed, efficiency, k):
MOD = 10**9 + 7
engs = sorted(zip(efficiency, speed), reverse=True)
h, total, best = [], 0, 0
for e, s in engs:
heapq.heappush(h, s); total += s
if len(h) > k: total -= heapq.heappop(h)
best = max(best, total * e)
return best % MODfunction maxPerformance(n, speed, efficiency, k) {
const MOD = 1_000_000_007n;
const engs = speed.map((s, i) => [efficiency[i], s]).sort((a, b) => b[0] - a[0]);
// simple sorted-array min-heap surrogate (small n)
const h = [];
let total = 0n, best = 0n;
for (const [e, s] of engs) {
h.push(s); h.sort((a, b) => a - b);
total += BigInt(s);
if (h.length > k) total -= BigInt(h.shift());
const cand = total * BigInt(e);
if (cand > best) best = cand;
}
return Number(best % MOD);
}class Solution {
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
long MOD = 1_000_000_007L;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> efficiency[b] - efficiency[a]);
PriorityQueue h = new PriorityQueue<>();
long total = 0, best = 0;
for (int i : idx) {
h.offer(speed[i]); total += speed[i];
if (h.size() > k) total -= h.poll();
best = Math.max(best, total * efficiency[i]);
}
return (int)(best % MOD);
}
} int maxPerformance(int n, vector& speed, vector& efficiency, int k) {
const long long MOD = 1000000007LL;
vector idx(n); iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) { return efficiency[a] > efficiency[b]; });
priority_queue, greater> h;
long long total = 0, best = 0;
for (int i : idx) {
h.push(speed[i]); total += speed[i];
if ((int)h.size() > k) { total -= h.top(); h.pop(); }
best = max(best, total * efficiency[i]);
}
return (int)(best % MOD);
} Explanation
Performance is (sum of speeds) × (min efficiency) over the chosen team. The hard part is that the minimum efficiency depends on who is in the team. The trick is to fix the minimum efficiency first.
We sort engineers by efficiency in descending order. As we sweep this list, the current engineer's efficiency is the smallest among everyone seen so far. So if this engineer is the team's weakest link, all teammates must come from earlier (higher-efficiency) engineers.
To maximize the speed sum under that assumption, we keep a min-heap of the chosen speeds. We add each engineer's speed; if the heap grows past k, we pop the smallest speed so only the top k speeds stay. We track a running total of the heap's speeds.
At every step the candidate answer is total × currentEfficiency, and we keep the best one seen.
Example: speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2], k=2. When we reach the engineer with efficiency 4 and speed 10, the best two speeds banked are 10 and 5 (sum 15), giving 15 × 4 = 60, which is the maximum.