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)