LeetCode 솔루션 분류

[9/11] 1383. Maximum Performance of a Team

컨텐츠 정보

본문

Hard
232663Add to ListShare

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 nspeed[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

 

Constraints:

  • 1 <= k <= n <= 105
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 105
  • 1 <= efficiency[i] <= 108
Accepted
71,933
Submissions
149,042
태그

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
Runtime: 979 ms, faster than 9.31% of Python3 online submissions for Maximum Performance of a Team.
Memory Usage: 30.5 MB, less than 43.72% of Python3 online submissions for Maximum Performance of a Team.
import heapq
class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        speed_sum = 0
        
        # stores speed
        min_heap = []
        heapq.heapify(min_heap)
        
        max_performance = 0
        
        for e,s in sorted(zip(efficiency, speed), key=lambda x:x[0], reverse=True):
            speed_sum += s
            heapq.heappush(min_heap, s)
            if len(min_heap) > k:
                speed_sum -= heapq.heappop(min_heap)
            max_performance = max(max_performance, speed_sum * e)
        
        return max_performance % (10**9+7)
LeetCode 솔루션 356 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0