題目敘述 IPO
新企業準備上市增資，初始資本是w，可以參加k個專案。
每個專案的獲利和投入成本分別記錄在profits和capital陣列。請問，在盡可能增資的情況下，最後最大的總資本是多少?
測試範例
Example 1:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
參加第一個專案 總資本成長到1單位
參加第三個專案 總資本成長到4單位
Example 2:
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6
參加第一個專案 總資本成長到1單位
參加第三個專案 總資本成長到3單位
參加第三個專案 總資本成長到6單位
約束條件
Constraints:
1 <= k <= 10^5
參數k值介於1~十萬之間。
0 <= w <= 10^9
參數w值介於1~十億之間。
n == profits.length
n == capital.length
n代表專案的數目。
1 <= n <= 10^5
最少一個專案，最多十萬個專案。
0 <= profits[i] <= 10^4
每個專案的獲利最少0元，最多一萬元。
0 <= capital[i] <= 10^9
每個專案的投入成本最少0元，最多十億元。
觀察
如何獲得最大資本?
有一個直覺的想法，在資金許可的情況下，盡可能投入回報收益最大的專案。
演算法 盡可能投入回報收益最大的專案
先對專案排序，投入成本小的專案優先考慮。
接著用堆積去篩選出回報收益最大的專案，選擇前k個收益最大的專案。
最後的總資本就是增資後的最大值。
程式碼 盡可能投入回報收益最大的專案
class Solution:
def findMaximizedCapital(self, k, W, Profits, Capital):
# heap for project profit
heap = []
projects = sorted(zip(Profits, Capital), key=lambda p: p[1])
i = 0
# Pick k projects at most.
for _ in range(k):
# Push available projects into heap
while i < len(projects) and projects[i][1] <= W:
heapq.heappush(heap, -projects[i][0])
i += 1
# Pick best project with maximal profit.
if heap:
W += abs( heapq.heappop(heap) )
# Maximal capital we have
return W
複雜度分析
時間複雜度: O( (k+n) log n)
排序前處理耗費O( n log n)
for loop挑選前k個最佳的專案耗費O( k log n)
空間複雜度: O(n)
維護一個minHeap，heap最大可能多達n個專案，所需空間為O(n)
關鍵知識點
在資金許可的情況下，盡可能投入回報收益最大的專案。
用Priority Queue，在實作中，就是heap，去挑選前k個可參與且收益最高的專案。
Reference
[1] IPO - LeetCode
