新股上市增資 IPO Leetcode #502 優先權佇列應用

Sophie Backes on Unsplash

題目敘述 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