前往
大廳
主題

LeetCode - 0502. IPO 解題心得

Not In My Back Yard | 2024-01-09 12:00:04 | 巴幣 0 | 人氣 74

題目連結:


題目意譯:
假設 LeetCode 即將開始它的首次公開募股(Initial Public Offerings,IPO)。為了以一些好價格賣股份給創投公司(Venture Capital,VC),Leetcode 想要在 IPO 之前進行一些專案來提升資本。由於它只有有限的資源,它只能在 IPO 前完成最多 k 個相異的專案。請幫助 LeetCode 設計出一個最佳方式來最大化完成最多 k 個相異專案後的總資本。

你被給定 n 個專案,其中第 i 個專案有著淨利潤 profits[i] 以及一個為了著手進行該專案的最小所需資本 capital[i]。

一開始你有 w 單位資本。每當你完成一個專案,你會獲得其淨利潤而該利潤將會直接加到你的總資本上。

請從給定的專案中挑出最多 k 個相異專案來做使得最終資本最大化,並回傳最終的最大化資本。

答案保證可以容納進一個 32 位元有號整數。

限制:
1 ≦ k ≦ 10 ^ 5
0 ≦ w ≦ 10 ^ 9
n == profits.length
n == capital.length
1 ≦ n ≦ 10 ^ 5
0 ≦ profits[i] ≦ 10 ^ 4
0 ≦ capital[i] ≦ 10 ^ 9



範例測資:
範例 1:
輸入: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
輸出: 4
解釋: 由於你一開始的資本為 0,你只能著手進行索引值 0 之專案。
完成該專案後,你將獲得 1 單位利潤而你的資本變為 1。
有了 1 單位資本後,你可以選擇進行索引值 1 或 2 的專案。
由於你只能選擇最多 2 個專案,你需要完成索引值 2 的專案來最大化資本。
因此,最終的最大化資本為 0 + 1 + 3 = 4。

範例 2:
輸入: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
輸出: 6


解題思維:
其實有點像這題。也就是說我們可以先將每一個專案按照所需資本由小排到大。然後根據「現在」的資本來把「剩下的」原本無法進行之專案丟進一個優先佇列(Priority Queue)中。然後我們從該優先佇列中拿出利潤最大者來做。

這樣一來做完 k 個專案(如果專案有滿 k 個以上的話;否則就是每一個專案都可以做)的資本便是最大的。因為每一個時刻我們都會在所有可以做的專案中挑出利潤最大的。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作