# Day 5: Maximum Performance of a Team

*Problem Link:*

*Problem 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`

. `speed[i]`

and `efficiency[i]`

represent the speed and efficiency of the `ith`

engineer respectively.

Choose **at most** `k`

different engineers out of the `n`

engineers to form a team with 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`

.

*Example 1:*

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

**Output:** 60

**Explanation:**

We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

*Example 2:*

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

**Output:** 68

**Explanation:**

This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

*Example 3:*

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

**Output:** 72

*Constraints:*

`- 1 <= <= k <= n <= 10^5`

- speed.length == n

- efficiency.length == n

- 1 <= speed[i] <= 10^5

- 1 <= efficiency[i] <= 10^8

*My Solution:*

`class Solution:`

def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

ord = sorted(zip(efficiency, speed), reverse=True)

print(ord)

spheap, totalSpeed, best = [], 0, 0

for eff, spd in ord:

heappush(spheap, spd)

if len(spheap) <= k: totalSpeed += spd

else: totalSpeed += spd - heappop(spheap)

best = max(best, totalSpeed * eff)

return best % 1000000007

*Explanation:*

The trick to this problem is to find a way to iterate through one of the values in order, then evaluate the other value for each combination and take the best result. If we sort the engineers by **efficiency**, we can iterate downward through the engineers while evaluating the combined speed i.e. **totalSpeed** of the group.

Since the index numbers between **speed** and **efficiency** correspond to each other, we shouldn’t just sort **efficiency**, instead, we can create another array of arrays i.e. ord, with both of them combined into one array, then sort it based on the efficiency.

As we iterate through the engineers in **ord** order and add them to the available pool, we know that all the engineers so far are at or higher than minEff, so we’re free to only choose the **k** fastest engineers for our group. To keep track of the sorted order of speeds of the engineers in our available pool, we can use a **min-heap** i.e. **spheap**. This way, we can eliminate the slowest engineer from our pool every time we add an engineer over the **k** limit. At each stop, we should also find the product of **totalSpeed** and the current minimum efficiency and update the **best** result if necessary.

It’s important to note that the instructions say “at most” **k** engineers, so we should start keeping track of **best** right away. Also, we should remember to **modulo 1e9+7** before we **return best**.

*Time Complexity: O(N * log(N))**where**N**is the length of**speed**or**efficiency**, for the sorting of**ord**and for the heap**Space Complexity: O(N)**for**ord**and**spheap*

That’s it!

If you are interested in solving more problems, do follow me and join me on this journey.

See you tomorrow!

Cheers!