Posted on

Description

Submission

class Solution {
    typedef pair<int, int> PII;
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        priority_queue<int> pq;
        int n = profits.size();
        vector<PII> pc; // capital, profits

        for(int i = 0; i < n; ++i) {
            pc.emplace_back(capital[i], profits[i]);
        }

        sort(pc.begin(), pc.end());
        
        int ptr = 0;
        for(int i = 0; i < min(k, n); ++i) {
            for(; ptr < n && pc[ptr].first <= w; ++ptr) {
                pq.emplace(pc[ptr].second);
            }
            if(pq.empty()) return w;
            w += pq.top();
            pq.pop();
        }

        return w;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *