Maximum Performance of a Team

Intuition

We could first sort all the engineers by their efficiency. We need to know the maximum sum of speed we can get with the minimum efficiency for each efficiency. To achieve this, we need to use a heap and keep the maximum speed sum with the efficiency as minimum efficiency.

Solution


import heapq


class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        eff_heap = []
        for i in range(n):
            heapq.heappush(eff_heap, [-efficiency[i], i])

        max_performance = float('-inf')
        speed_heap = []
        s = 0
        while eff_heap:
            eff, i = heapq.heappop(eff_heap)
            eff = -eff
            s += speed[i]
            heapq.heappush(speed_heap, speed[i])
            if len(speed_heap) > k:
                tmp = heapq.heappop(speed_heap)
                s -= tmp
            max_performance = max(max_performance, s * eff)
        return max_performance % ((10 ** 9) + 7)