502. IPO

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;
    }
};

• T: $O(n \cdot \log n)$
• S: $O(n)$