Maximum Performance of a Team

Problem Id: 1383 Difficulty: Hard Tag: Greedy Tag: Sort


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.


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)