O(n log n) Solution


  • 1
    K
    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            int n = Profits.size();
            vector<pair<int, int>> a;
            for (int i = 0; i < n; ++i) {
                a.push_back(make_pair(Capital[i], Profits[i]));
            }
            sort(begin(a), end(a));
            
            priority_queue<int> heap;
            int j=0;
            for (j = 0; j < n; ++j) {
                if (a[j].first <= W) heap.push(a[j].second);
                else break;
            }
            
            int maxCap = W;
            while (heap.size() > 0 && k > 0) {
                auto x = heap.top(); heap.pop();
                maxCap += x;
                --k;
                
                for (; j < n; ++j) {
                    if (a[j].first <= maxCap) heap.push(a[j].second);
                    else break;
                }
            }
            return maxCap;
        }
    };

Log in to reply
 

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