C++ greedy, very easy to understand with comments


  • 0
    P

    The problem is explained well by others. Here is how I visualized it.
    There are certain projects that we can undertake, it depends on the current money we get. Each project gives us a payout in addition to what we originally had.
    So -- "Pick the best possible project based on the payout which we can undertake, do it and count 1 project."
    Thus we need :

    1. Ordering of projects so that we can easily choose which ones to pick. (we sort).
    2. Best possible project from the ones we could pick in step 1.

    To do step one, we create pair of Capital and Profits.
    To do step two, we maintain a heap and keep popping the best one yet.

    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            vector<pair<int, int>> vpair;
            auto cmp = [](const pair<int, int>& a, const pair <int, int>& b){ return a.first < b.first;}; \\comparator.
            priority_queue<int, std::vector<int>, std::less<int>> pq; //priority queue that yields best each time.
            for(int i = 0; i < Capital.size(); ++i){
                vpair.emplace_back(Capital[i], Profits[i]); 
            }
            int out = 0;
            sort(vpair.begin(), vpair.end()); //Sort.
            int j = 0;
            while(k > 0){
                while(j < vpair.size() && vpair[j].first <= W) 
                    pq.push(vpair[j++].second); // push till we cannot push anymore.
                if(!pq.empty()){
                    W += pq.top(); \\add to our result.
                    pq.pop();
                }
                k--; //we reduce k unconditionally so that we break the loop sometime. If we were unable to pop() once,
    // we will never be able to pop again, 
    //so it exits elegantly, without putting more conditions.
            }
            return W;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.