Posted on 2023-02-24 00:07
Uriel 閱讀(52)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code
有n個projects，每個需要capacity[i]才能啟動，獲利profits[i]，初始擁有w capacity，問完成最多k個projects可以最多獲利多少
利用heap（or優(yōu)先隊列）的貪心
先按照capacity從小到大對projects排序，然后從第一個project開始，如果capacity小于當(dāng)前的w，則加入heap，直到capacity的要求大于當(dāng)前w，然后去完成heap頂端的project
1 #502
2 #Runtime: 1335 ms (Beats 51.90%)
3 #Memory: 37.9 MB (Beats 69.62%)
4
5 class Solution(object):
6 def findMaximizedCapital(self, k, w, profits, capital):
7 """
8 :type k: int
9 :type w: int
10 :type profits: List[int]
11 :type capital: List[int]
12 :rtype: int
13 """
14 n = len(profits)
15 proj = list(zip(capital, profits))
16 proj.sort()
17 j = 0
18 q = []
19 for i in range(k):
20 while j < n and proj[j][0] <= w:
21 heappush(q, -proj[j][1])
22 j += 1
23 if not q:
24 break
25 w += -heappop(q)
26 return w