WHY this O(nlogn + nk) Solution passed AND fast


  • 0
    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            vector<pair<int, int>> pairs;
            
            for(int i=0; i<Profits.size(); i++){
                pairs.push_back({Profits[i], Capital[i]});
            }
            
            sort(pairs.begin(), pairs.end());
            
            for(int i=pairs.size()-1; i>=0; --i){
                if(W>=pairs[i].second && k>0){
                    W += pairs[i].first;
                    k--;
                    pairs.erase(pairs.begin()+i);
                    // if(pairs.empty())
                    //     break;
                    i = pairs.size();
                }
            }
            return W;
        }
    };
    

Log in to reply
 

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