C++ | 100% Faster | Priority Queue | Easy Step By Step Explanation
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe key to maximizing capital before LeetCode\'s IPO lies in strategically select
![Zombie Upvote.png](https://assets.leetcode.com/users/images/354aca00-ef18-4232-908c-5bfb65521cf5_1718410478.9977033.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key to maximizing capital before LeetCode\'s IPO lies in strategically selecting projects that offer the highest potential return on investment (ROI) within the constraints of limited resources. We need to consider projects that LeetCode can afford (capital requirement <= current capital) and prioritize those with the most significant profit.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Data Preprocessing:**\n    - Combine capital and profit information into pairs for efficient processing.\n    - Sort these pairs in ascending order of capital requirement.  This ensures we consider affordable projects first.\n2. **Priority Queue and Greedy Selection:**\n    - Initialize a priority queue (pq) to store project profits. This data structure prioritizes the highest profits, allowing for greedy selection during project execution.\n    - Iterate through the sorted pairs (arr) up to k times (number of allowed projects):\n        - **While current capital (w) allows undertaking new projects (i.e., capital[i] <= w):**\n            - Add the corresponding project profit (arr[i].second) to the priority queue.\n        - If the queue becomes empty (no more affordable projects), we\'ve exhausted all viable options, so break the loop.\n        - Select the most profitable project from the queue (highest profit at the queue\'s top) using pq.top(). Add this profit to the current capital (w += pq.top()).\n        - Remove the selected project from the queue (pq.pop()).\n\n# Complexity\n- Time complexity: **O(n log n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(n)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#pragma GCC optimize("03", "unroll-loops")\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {\n        int n = profits.size();   \n        vector<pair<int, int>> arr;\n        for (int i = 0; i < n; i++) {\n            arr.push_back({capital[i], profits[i]});\n        }\n        sort(arr.begin(), arr.end());\n        priority_queue<int> pq;\n        int i = 0;\n        while (k--) {\n            while (i < n && arr[i].first <= w) {\n                pq.push(arr[i].second);\n                i++;\n            }\n            if (pq.empty()) {\n                break;\n            }\n            w += pq.top();\n            pq.pop();\n        }\n        return w;\n    }\n};\nauto init = [](){\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C++']