Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Maximum Performance of a Team

Maximum Performance of a Team

Master this topic with zero to advance depth.

Maximum Performance of a Team

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 10^9 + 7.

Visual Representation

n=6, k=2, speed=[2,10,3,1,5,8], efficiency=[5,4,3,9,7,2] Key Insight: Sort by efficiency descending. For each engineer i as the "min efficiency" of the group, pick the k fastest engineers from 0..i (including i). Sorted by eff desc: (9,1),(7,5),(5,2),(4,10),(3,3),(2,8) - Min eff = 9: Team = [(1,9)]. Perf = 1*9 = 9 - Min eff = 7: Team = [(1,9),(5,7)]. Sum speeds=6. Perf=6*7=42 - Min eff = 5: Team = [(2,5),(5,7),(1,9)]. Speeds=[1,5,2]. Sum k=2 fastest=5+2=7. Perf=7*5=35 - Min eff = 4: Team picks (10,4) as one, need 2 fastest. Max perf = (10+5)*4 = 60
Hard

Examples

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

Level I: Brute Force - Check All Subsets

Intuition

Try all possible subsets of at most k engineers from the n engineers. For each subset, compute performance = (sum of speeds) * (minimum efficiency). Return the maximum. This is correct but exponential in complexity.

⏱ O(2^N * N) — exponential, infeasible for large N💾 O(N) for recursion stack

Detailed Dry Run

n=4, k=2, speed=[2,10,3,1], efficiency=[5,4,3,9] Subsets of size 1: {0}->25=10, {1}->104=40, {2}->33=9, {3}->19=9 Subsets of size 2: {0,1}->12min(5,4)=48, {0,2}->5min(5,3)=15, {0,3}->3min(5,9)=15, {1,2}->13min(4,3)=39, {1,3}->11min(4,9)=44, {2,3}->4min(3,9)=12 Max = 48

java
public class Main {
    static final int MOD = 1_000_000_007;
    static int n, k;
    static int[] speed, efficiency;
    static long maxPerf = 0;
    
    static void dfs(int idx, int count, long sumSpeed, int minEff) {
        if (count > 0) {
            maxPerf = Math.max(maxPerf, sumSpeed * minEff);
        }
        if (count == k || idx == n) return;
        
        for (int i = idx; i < n; i++) {
            dfs(i + 1, count + 1, sumSpeed + speed[i], Math.min(minEff, efficiency[i]));
        }
    }
    
    public static int maxPerformance(int n_, int[] sp, int[] eff, int k_) {
        n = n_; k = k_; speed = sp; efficiency = eff;
        maxPerf = 0;
        dfs(0, 0, 0, Integer.MAX_VALUE);
        return (int)(maxPerf % MOD);
    }

    public static void main(String[] args) {
        System.out.println(maxPerformance(6, new int[]{2,10,3,1,5,8}, new int[]{5,4,3,9,7,2}, 2)); // 60
    }
}
Approach 2

Level II: Sort by Efficiency and Search K-Fastest

Intuition

To improve on brute force, we can sort the engineers by their efficiency in descending order. By doing so, for each engineer i, if we consider them as the minimum efficiency in the team, we only need to look at engineers from 0 to i (who all have efficiency >= eff[i]) and pick the k fastest ones.

⏱ O(N^2 log N) because for each of the N engineers, we sort the prefix of speeds to find the k fastest💾 O(N) to store the engineers and prefix speeds

Detailed Dry Run

n=4, k=2, speed=[2,10,3,1], efficiency=[5,4,3,9] Sorted: (9,1), (5,2), (4,10), (3,3)

  1. i=0, Eff=9: prefix=[1]. Sum k=2 fastest = 1. Perf = 1*9=9.
  2. i=1, Eff=5: prefix=[1,2]. Sum k=2 fastest = 3. Perf = 3*5=15.
  3. i=2, Eff=4: prefix=[1,2,10]. Sum k=2 fastest = 12. Perf = 12*4=48.
  4. i=3, Eff=3: prefix=[1,2,10,3]. Sum k=2 fastest = 13. Perf = 13*3=39. Max = 48.
java
import java.util.*;

public class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        long MOD = 1_000_000_007L;
        int[][] engineers = new int[n][2];
        for (int i = 0; i < n; i++) {
            engineers[i][0] = efficiency[i];
            engineers[i][1] = speed[i];
        }
        Arrays.sort(engineers, (a, b) -> b[0] - a[0]);

        long maxPerf = 0;
        List<Integer> prefixSpeeds = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            prefixSpeeds.add(engineers[i][1]);
            Collections.sort(prefixSpeeds, Collections.reverseOrder());
            
            long sumSpeed = 0;
            for (int j = 0; j < Math.min(k, prefixSpeeds.size()); j++) {
                sumSpeed += prefixSpeeds.get(j);
            }
            maxPerf = Math.max(maxPerf, sumSpeed * engineers[i][0]);
        }
        return (int) (maxPerf % MOD);
    }
}
Approach 3

Level III: Sort by Efficiency + Min-Heap (Optimal)

Intuition

Key Insight: When we pick any subset of engineers, the performance is bottlenecked by the minimum efficiency. If we fix the minimum efficiency to be efficiency[i], then we should include engineer i in the team AND pick the k-1 fastest engineers from all engineers who have efficiency >= efficiency[i].

If we sort engineers by efficiency in descending order, as we iterate through them, the current engineer i has the minimum efficiency seen so far. We need the maximum sum of speeds from engineer 0 to i. We maintain a Min-Heap of size k storing speeds — when the heap exceeds k, we pop the smallest speed. This ensures our heap always holds the k largest speeds.

⏱ O(N log N) for sorting and O(N log K) for heap operations💾 O(K) for the Min-Heap

Detailed Dry Run

n=6, k=2, sp=[2,10,3,1,5,8], eff=[5,4,3,9,7,2] Sort by eff desc: [(9,1),(7,5),(5,2),(4,10),(3,3),(2,8)] min_heap=[], speed_sum=0, best=0

  1. (9,sp=1): push 1. sum=1. size=1<=2. perf=1*9=9. best=9.
  2. (7,sp=5): push 5. sum=6. size=2<=2. perf=6*7=42. best=42.
  3. (5,sp=2): push 2. sum=8. size=3>2. pop min(1). sum=7. perf=7*5=35. best=42.
  4. (4,sp=10): push 10. sum=17. size=3>2. pop min(2). sum=15. perf=15*4=60. best=60.
  5. (3,sp=3): push 3. sum=18. size=3>2. pop min(3). sum=15. perf=15*3=45. best=60. Return 60 % MOD = 60
java
import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;
    
    public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> efficiency[b] - efficiency[a]);
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        long speedSum = 0, best = 0;
        
        for (int idx : indices) {
            minHeap.offer(speed[idx]);
            speedSum += speed[idx];
            
            if (minHeap.size() > k) {
                speedSum -= minHeap.poll();
            }
            
            best = Math.max(best, speedSum * efficiency[idx]);
        }
        
        return (int)(best % MOD);
    }

    public static void main(String[] args) {
        System.out.println(maxPerformance(6, new int[]{2,10,3,1,5,8}, new int[]{5,4,3,9,7,2}, 2)); // 60
    }
}
← Previous QuestionKth Smallest Element in Sorted Matrix
Next Question →Minimum Interval to Include Each Query