Sorting + One O(k)-size Priority Queue Solution


  • 2
    W

    There are many excellent solutions based on two priority queue solution, however, we do not need to maintain two priority queues that contain all projects.

    • If we sort the Capital in increasing order, we can insert "doable" project into the pq until we meet an "undoable" project.

    • We need only one priority queue (multiset) to maintain the "doable" projects. Here the key observation is: we can only pop k times. So we do not need to maintain a large priority queue. Every time we find the size of PQ is larger than k (k is shrinking!!!), we just erase the project with least profit from the PQ.

    • Note that the worst case time complexity is still O(NlogN), because we need to sort : )

    class Solution {
    public:
        struct Node {int profit, capital;};
    
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            if(Profits.empty() || Capital.empty()) return W;
            vector<Node*> projects;
            for(int i = 0; i < Profits.size(); i++) 
                projects.push_back(new Node({Profits[i], Capital[i]}));
            multiset<int> pq;
            sort(projects.begin(), projects.end(), [&](Node* n1, Node* n2) {return n1->capital < n2->capital;});
            for(auto start = projects.begin(); k > 0; k--) {
                for(; start != projects.end() && (*start)->capital <= W; start++) {
                    pq.insert((*start)->profit);
                    if(pq.size() > k) pq.erase(pq.begin());
                } 
                if(pq.empty()) break;
                W += *pq.rbegin();
                pq.erase(prev(pq.end()));
            }
            return W;
        }
    };
    

  • 1

    @wangxinbo
    multiset is not a PriorityQueue, instead it's a BST implementation. In your code you can access both min and max.


  • 0
    Z

    It seems that it is even a little slower than priority queue solution. Maybe multiset is not as efficient as heap.

    @wangxinbo said in Sorting + One O(k)-size Priority Queue Solution:

    class Solution {
    public:
    struct Node {int profit, capital;};

    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        if(Profits.empty() || Capital.empty()) return W;
        vector<Node*> projects;
        for(int i = 0; i < Profits.size(); i++) 
            projects.push_back(new Node({Profits[i], Capital[i]}));
        multiset<int> pq;
        sort(projects.begin(), projects.end(), [&](Node* n1, Node* n2) {return n1->capital < n2->capital;});
        for(auto start = projects.begin(); k > 0; k--) {
            for(; start != projects.end() && (*start)->capital <= W; start++) {
                pq.insert((*start)->profit);
                if(pq.size() > k) pq.erase(pq.begin());
            } 
            if(pq.empty()) break;
            W += *pq.rbegin();
            pq.erase(prev(pq.end()));
        }
        return W;
    }
    

    };


Log in to reply
 

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