Solution: Maximum Performance of a Team

Statement

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. The value speed[i] represents the speed of the i-th engineer, and efficiency[i] represents their efficiency.

To form a team with the maximum performance, you need to select at most k different engineers from the n engineers.

The performance of a team is calculated as follows:

The sum of the selected engineers’ speeds $\times$ the minimum efficiency among the selected engineers

Return the maximum performance of the team. As the result can be a very large number, return it modulo $(10^9 + 7)$.

Constraints:

• $1 \leq$ k $\leq$ n $\leq 10^3$

• speed.length $==$ n

• efficiency.length $==$ n

• $1 \leq$ speed[i] $\leq 10^3$

• $1 \leq$ efficiency[i] $\leq 10^4$

Solution

The core idea behind the solution is to combine the Top-K Elements pattern with a greedy strategy to maximize the overall team performance. As a team's performance is calculated as the sum of selected engineers’ speeds multiplied by the minimum efficiency among them, the goal is to form a group of up to k engineers with the highest speeds, while keeping the lowest efficiency in the group as high as possible. To achieve this, all engineers are sorted in descending order of efficiency. This guarantees that as we iterate through the list, the current engineer’s efficiency becomes the lowest efficiency for any team that includes them and any previously considered engineers, because all subsequent engineers have equal or lower efficiency.

We use a min heap to maintain the top k speeds, which efficiently keeps track of the smallest speed in the current selection. The smallest speed is removed if the heap grows beyond k, ensuring only the most impactful speeds are retained. As we process each engineer, we update the total speed and calculate the potential performance by multiplying it by the current engineer’s efficiency. The highest performance during this process is recorded and returned at the end.

The steps of the algorithm are as follows:

1. Combine efficiency[i] and speed[i] into tuples as (efficiency, speed) and sort the engineers list in descending order of efficiency to process higher-efficiency engineers first.

2. Initialize the following variables:

   1. maxPerf: To keep track of the maximum performance encountered so far.

   2. speedSum: A running total of the speeds of engineers currently in the team.

   3. minHeap: A min heap used to store the top k speeds efficiently, allowing fast removal of the smallest speed when needed.

3. Iterate through the sorted engineers. For each (eff, spd) tuple in the sorted list:

   1. If the heap already contains k elements, remove the smallest speed to make room for the current engineer’s speed, and subtract it from the running total (speedSum). This ensures that the team always contains at most k engineers.

   2. Push the current engineer’s spd into minHeap and update speedSum by adding spd.

   3. Compute performance as speedSum * eff, where eff is the efficiency of the current engineer (who is now the least efficient in the current team).

   4. Update maxPerf if the newly computed performance is higher than the current maximum.

4. Return maxPerf % (10^9 + 7) to ensure the result stays within standard integer bounds, especially for large inputs.

Let’s look at the illustration below to better understand the solution.