Day 5: Maximum Performance of a Team

Problem Link:

Explore - LeetCode

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!