🔗 🔴 502. IPO

tags: `貪心(Greedy)` `排序(Sorting)` `堆積(Heap)`

題意

某間公司即將進行首次 公開募股(IPO) ，為了以較高的價格出售股份，公司希望在 IPO 之前完成一些項目以增加其資本。由於資源有限，它最多只能在 IPO 前完成 $k$ 個不同的項目。請幫助公司設計最佳方式，在最多完成 $k$ 個不同項目的情況下，最大化其總資本。

給定 $n$ 個項目，其中第 $i$ 個項目有純利潤 $\text{profits}[i]$ 且需要最小資本 $\text{capital}[i]$ 才能開始。

另外給定一個整數 $w$ ，表示公司的初始資本。當完成一個項目時，公司將獲得其純利潤，並將利潤添加到公司的總資本中。注意，起始資本並不會隨著進行項目而被消耗。

從給定的項目中選擇最多 $k$ 個不同的項目，以最大化公司的最終資本，並返回最終最大化的資本。

答案保證在 $32$ 位有號整數範圍內。

思路：貪心(Greedy) + 排序(Sorting) + 堆積(Heap)

首先確定思路，在擁有 $w$ 的資本時，我們能選擇的項目 $i$ 必須滿足 $\text{capital}[i] \leq w$ ，而為使獲得的利潤最高，以及下一次選擇項目時，資本最大，我們應選擇在這些符合條件的項目中，利潤最大的項目。

因此我們可以將所有項目按照 $\text{capital}$ 進行排序(Sorting) ，然後遍歷這些項目，將可以進行的項目放入一個最大堆積(Max Heap) 中，Max Heap中存放的是這些項目的利潤。我們每次從中取出利潤最大的項目執行，然後更新公司的資本。我們重複這個過程 $k$ 次，直到達到最大化資本或者無法再執行項目為止。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n + k \log n)$ $O (n lo g n + k lo g n)$ ，其中 $n$ $n$ 是項目的數量。
- 對所有項目按照資本進行排序需要 $\mathcal{O}(n \log n)$ 的時間。
- 對於每個項目最多需要進行一次 heappush 操作，每次操作的時間複雜度為 $\mathcal{O}(\log n)$ ，最多執行 $n$ 次，因此需要 $\mathcal{O}(n \log n)$ 的時間。
- 對於每個項目最多需要進行一次 heappop 操作，每次操作的時間複雜度為 $\mathcal{O}(\log n)$ ，最多執行 $k$ 次，因此需要 $\mathcal{O}(k \log n)$ 的時間。
空間複雜度： $\mathcal{O}(n)$ ，需要一個大小為 $n$ 的陣列來存儲所有項目。

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        n = len(profits)
        projects = [(c, p) for c, p in zip(capital, profits)]
        projects.sort() # Sort the projects by capital in ascending order

        ans, idx = w, 0
        hp = [] # Max heap
        for _ in range(k):
            while idx < n and projects[idx][0] <= ans: # Add all the projects that can be done now
                heappush(hp, -projects[idx][1]) # Max heap
                idx += 1
            if not hp: # No project can be done
                break
            ans += -heappop(hp) # Do the project with the maximum profit
        return ans

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int, int>> projects;
        for (int i = 0; i < n; i++)
            projects.push_back({capital[i], profits[i]});
        // Sort the projects by capital in ascending order
        sort(projects.begin(), projects.end());

        int ans = w, idx = 0;
        priority_queue<int> hp;  // Max heap
        for (int i = 0; i < k; i++) {
            // Add all the projects that can be done now
            while (idx < n && projects[idx].first <= ans)
                hp.push(projects[idx++].second);
            // No project can be done
            if (hp.empty()) break;
            // Do the project with the maximum profit
            ans += hp.top();
            hp.pop();
        }
        return ans;
    }
};