1383. Maximum Performance of a Team.py

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 the 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 109 + 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


  
from sortedcontainers import SortedList
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

        cur_sum, h = 0, []
        ans = -float('inf')
        
        for i, j in sorted(zip(efficiency, speed),reverse=True):
            while len(h) > k-1:
                cur_sum -= heappop(h)
            heappush(h, j)
            cur_sum += j
            ans = max(ans, cur_sum * i)
            
        return ans % (10**9+7)

        
        effi = [(e, i) for i, e in enumerate(efficiency)]
        effi.sort()
        spe = [speed[i] for _, i in effi]
        sortspeed = SortedList(spe)
        #print(effi)
        #print(sortspeed)
        #print(spe)
        ret = 0
        for x in range(len(effi)):
            ans = 0
            sortspeed.remove(spe[x])
            e , _ = effi[x]
            
            sp =  spe[x]
            total = 0
            j = len(sortspeed) - 1
            
            while total < k-1 and j >= 0:
                sp += sortspeed[j]
                j-=1
                total+=1
            ans += sp * e
            
            ret = max(ret, ans)
            #print(ans, e, spe[x], sortspeed)
        return ret % (10**9+7)