[LeetCode] 502. IPO

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/ipo/

Solution:
The profits are the pure profits, which means the costs have already been taken into account. Since this question is looking for the maximum profit, we can first sort the projects based on their costs. In order to keep the information of the corresponding profits, we need a pair structure to connect them. Then for all the projects that are available right now(costs smaller than the capital in hand), we can choose the one with maximum profit. Then we need to update the capital, which will possible make more projects available (that were not previously.) Then we can repeat the above processes starting with find the maximum profit among the projects available, until reaching k projects or no more projects available.

Code:

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        int res = W, l = Profits.size();
        vector<pair<int, int>> v;
        for(int i=0; i<l; ++i) v.push_back(make_pair(Capital[i], Profits[i]));
        sort(v.begin(), v.end());
        priority_queue<int> q;//q.top() is the maximum;
        int i = 0;
        for(; i<l; ++i){
            if(v[i].first<=res) q.push(v[i].second);
            else break;
        }
        while(q.size()&&k){
            int t = q.top();
            q.pop();
            res +=t;
            --k;
            for(; i<l; ++i){
                if(v[i].first<=res) q.push(v[i].second);
                else break;
            }
        }
        return res;
    }
};