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

• 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;
}
};
``````

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

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

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;
}
``````

};

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