Maximum Performance of a Team

Problem

Choose at most k engineers. Performance = (sum of speeds) * (minimum efficiency). Maximize performance.

Key insight (Greedy): Sort by efficiency descending. For each engineer as "minimum efficiency", greedily include up to k engineers with highest speeds from those seen so far. Use min-heap of size k on speeds.

Solutions

// C++
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
    vector<pair<int,int>> eng(n);
    for (int i=0;i<n;i++) eng[i]={efficiency[i],speed[i]};
    sort(eng.rbegin(),eng.rend());
    priority_queue<int,vector<int>,greater<int>> minH;
    long sum=0,ans=0;
    for (auto&[e,s]:eng) {
        minH.push(s); sum+=s;
        if((int)minH.size()>k){sum-=minH.top();minH.pop();}
        ans=max(ans,sum*(long)e);
    }
    return ans%(long)(1e9+7);
}

// Java
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
    int[][] eng = new int[n][2];
    for(int i=0;i<n;i++) eng[i]=new int[]{efficiency[i],speed[i]};
    Arrays.sort(eng,(a,b)->b[0]-a[0]);
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    long sum=0,ans=0;
    for(int[]e:eng){
        minH.offer(e[1]); sum+=e[1];
        if(minH.size()>k){sum-=minH.poll();}
        ans=Math.max(ans,sum*e[0]);
    }
    return (int)(ans%(1000000007L));
}

# Python
import heapq

def maxPerformance(n, speed, efficiency, k):
    MOD = 10**9 + 7
    engineers = sorted(zip(efficiency, speed), reverse=True)
    heap = []
    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)
        best = max(best, speed_sum * eff)
    return best % MOD

// JavaScript
function maxPerformance(n, speed, efficiency, k) {
    const MOD = BigInt(1e9 + 7);
    const eng = efficiency.map((e, i) => [e, speed[i]]).sort((a, b) => b[0] - a[0]);
    const heap = []; // min-heap of speeds
    let sum = 0n, best = 0n;
    for (const [e, s] of eng) {
        // insert into sorted heap
        let pos = heap.findIndex(x => x >= s);
        if (pos === -1) heap.push(s); else heap.splice(pos, 0, s);
        sum += BigInt(s);
        if (heap.length > k) sum -= BigInt(heap.shift());
        const perf = sum * BigInt(e);
        if (perf > best) best = perf;
    }
    return Number(best % MOD);
}

Complexity

Time: O(n log n + n log k)
Space: O(k)