LeetCode 솔루션 분류
[9/11] 1383. Maximum Performance of a Team
본문
Hard
232663Add to ListShareYou 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
Constraints:
1 <= k <= n <= 105speed.length == nefficiency.length == n1 <= speed[i] <= 1051 <= efficiency[i] <= 108
Accepted
71,933
Submissions
149,042
태그
#Amazon
관련자료
-
링크
댓글 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.
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)
