✅[C++] Greedy using Priority Queue
What? \nThe question wants us to find the maximum capital we can make by doing at most k projects. Since each project has a profit >= 0, therefore we will choos
**What?** \nThe question wants us to find the maximum capital we can make by doing at most k projects. Since each project has a profit `>= 0`, therefore we will choose exact k projects because each project will contribute something to our answer. Greedy appraoch would be a better choice here. \n\n**Why Greedy?** \nThe first thing that stops us from using DP is constraints. The things that we would need to memoize are \n`1 <= k <= 10`<sup>5</sup>\n`0 <= w <= 10`<sup>9</sup>\n`1 <= n <= 10`<sup>5</sup>\nAnd these are not feasible constraints to be stored. At max, we can solve upto 10<sup>6</sup>. And here, since we will need to store three of them, we would not be able to. \nThen we can see, that in this question, if we just keep on adding the maximum profit we can get from every possible project, we will ultimately have the maximum profit that we can gain. We can note that using priority queue here, would enusre that we choose the most profitable project possible from current `w`. Priority queue stores the data in decreasing order, so it may be possible that we choose a project, lets say `j` which has the profit greater that a project, lets say `i`, such that `i<j`. But this will not affect our final answer as we have to return the maximum profit. (A+B == B+A, so order doesn\'t really matter here).\n\n**How?**\nSo, we store the capital of each project with its respective profit into another array of pairs, and sort it based on capitals. This way, we will have the lower capital projects first so that we have something to start from. Now, we make a max heap and while our current capital supports us to choose some projexts, we iterate over all of those projects(that we can choose from with current capital) and keep pushing them in our heap. Next, when we are finished iterating over them, we pick the projext having the maximum profit, we choose that project and add its profit to our current capital. \n\n```\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {\n        vector <pair <int,int>> arr;\n        for(int i = 0; i<profits.size(); i++) arr.push_back({capital[i],profits[i]});\n        sort(arr.begin(),arr.end());\n        \n        priority_queue <int> q;\n        int ans = 0, i=0;\n        while(i<arr.size() and k){\n            if(w>=arr[i].first) q.push(arr[i++].second);\n            else{\n\t\t\t\t// This condition will check if we had enough capital to choose any project or not. If not, we directly return the current capital.\n                if(q.empty()) return w;\n                \n                w += q.top();\n                q.pop();\n                k--;\n            }\n        }\n\t\t// Here, we check if we could still choose some projects\n        while(k-- and !q.empty()){\n            w += q.top();\n            q.pop();\n        }\n        return w;\n    }\n};\n```
['Greedy', 'C', 'Heap (Priority Queue)']