# [502\. IPO](https://leetcode.com/problems/ipo/)

假設你是一個專案經理，負責選擇和啟動項目來增加你的資金。在開始時，你有若干初始資金 `w`，以及一個專案池，每個專案有一定的成本和潛在的利潤。

你的目標是用這些初始資金啟動最多 k 個項目，使你的總資金最大化。

給予若干項目，分別由其成本`capital[i]`和潛在利潤`profits[i]`表示。你必須在啟動某個項目前確保你擁有足夠的資金來支付這個項目的成本。一旦啟動，你可以立即獲得該項目的利潤。你的總資金可以用來啟動其他項目。

題目給了一個例子

k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]

- 起始資金 `w` 為 `0`。
- 最多可以選 `k = 2` 個專案項目。
- 三個專案可以獲得的利潤分別是 `[1, 2, 3]`。
- 三個專案需要花費的成本分別是 `[0, 1, 1]`。

因為起始資金為 0，所以一開始只能選第 `0` 個專案，獲利 `1`，接下來選第 2 個專案，獲利 `3`。

題目問總共獲得多少資金，所以是`0 + 1 + 3 = 4`。

- 初始化：將 {capital, profits} pair 在一起成一個 vector `projects` 比較好處理，之後可以由小到大按照 capital 排序。
- 初始化一個 prority queue，當啟動 project 的成本小於等於 `w` 的時候，將獲得的利潤推到 queue。
- 雙指針，一個指針指向 k 有多少個 project，另一個指向 projects。
- 最後將獲得的資金加到 `w`上。

:::spoiler Solution

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        
        // 將 {capital, profits} pair 在一起比較好處理 (排序)
        vector<pair<int, int>> projects;
        
        for (int i = 0; i < n; i++)
        {
            projects.push_back({capital[i], profits[i]});
        }
        
        // 排序後，capital 小的會放前面
        sort(projects.begin(), projects.end());
        
        priority_queue<int> q;
        
        int j = 0;
        
        // 最多 k 個專案
        for (int i = 0; i < k; i++)
        {
            // 當啟動 project 的成本 projects[ptr].first 小於等於 w 的時候
            while (j < n && projects[j].first <= w)
            {
                // 將獲得的利潤推到 queue
                q.push(projects[j].second);
                // 指標++，移動到下一個 project
                j++;
            }
            // 直到 queue 裡面沒有 project
            if (q.empty()) break;
            
            // 將獲得的利潤加到 w
            w += q.top(); q.pop();
        }
        // 最後 return 總共獲得多少的資金 w
        return w;
    }
};

- 時間複雜度：$O(n \cdot \log n)$
- 空間複雜度：$O(n)$
:::