DSA problem
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 i-th engineer respectively. Choose at most k different engineers out of the n engineers to form a team with the maximum performance.
The performance of a team is the sum of their engineers' 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.
The slick observation is: if we sort the engineers by efficiency in descending order, then as we sweep through them, the engineer currently being considered always has the lowest efficiency among the engineers seen so far. So if we pick this engineer to participate, his efficiency is the team's minimum efficiency. That converts the problem into: at each step, what is the maximum sum of up to k speeds among engineers seen so far, multiplied by the current efficiency?
We maintain a min-heap of the speeds we have included and a running sum. For each engineer in sorted-by-efficiency order, push his speed and add it to the sum. If the heap size exceeds k, pop the smallest speed and subtract it from the sum — this enforces the "at most k" constraint while keeping the sum maximal. The answer is the maximum value of sum * currentEfficiency across all positions. Time complexity is O(n log n) (sorting plus heap operations).
Examples
n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 260n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 368n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 472Constraints
- 1 <= k <= n <= 10^5
- speed.length == n
- efficiency.length == n
- 1 <= speed[i] <= 10^5
- 1 <= efficiency[i] <= 10^8
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.