C++ solution 39ms:with sort and priority_queue


  • 0

    First we create pairs to store profits and capital,then sort them by capital.Each time we try to start a project,get all pairs no bigger than the current W into priority_queue,and pick out the most profit to update W.

    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& profit, vector<int>& capital) 
        {
            int n = static_cast<int>(profit.size());
            vector<pair<int,int>> benefit;
            benefit.reserve(n);
            for(int i = 0;i < n;++i)
                benefit.emplace_back(capital[i],profit[i]);
            sort(benefit.begin(),benefit.end());
            
            priority_queue<int> pq;
            int i = 0;
            while(k-- > 0)
            {
                for(;i < n && benefit[i].first <= W;++i) 
                    pq.push(benefit[i].second);
                if(!pq.empty())
                {
                    W += pq.top();
                    pq.pop();
                }
            }
            
            return W;
        }
    };
    

Log in to reply
 

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