# Very Simple (Greedy) Java Solution using two PriorityQueues

• The idea is each time we find a project with `max` profit and within current capital capability.
Algorithm:

1. Create (capital, profit) pairs and put them into PriorityQueue `pqCap`. This PriorityQueue sort by capital increasingly.
2. Keep polling pairs from `pqCap` until the project out of current capital capability. Put them into
PriorityQueue `pqPro` which sort by profit decreasingly.
3. Poll one from `pqPro`, it's guaranteed to be the project with `max` profit and within current capital capability. Add the profit to capital `W`.
4. Repeat step 2 and 3 till finish `k` steps or no suitable project (pqPro.isEmpty()).

Time Complexity: For worst case, each project will be inserted and polled from both PriorityQueues once, so the overall runtime complexity should be `O(NlgN)`, N is number of projects.

``````public class Solution {
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
PriorityQueue<int[]> pqPro = new PriorityQueue<>((a, b) -> (b[1] - a[1]));

for (int i = 0; i < Profits.length; i++) {
}

for (int i = 0; i < k; i++) {
while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
}

if (pqPro.isEmpty()) break;

W += pqPro.poll()[1];
}

return W;
}
}
``````

• @shawngao brilliant solution

• Brilliant solution! : )

• Really awesome. Make it a little bit more OO:

``````public class Solution {
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<Point> q1 = new PriorityQueue<>((a, b) -> (a.cap - b.cap));
PriorityQueue<Point> q2 = new PriorityQueue<>((a, b) -> (b.pro - a.pro));
for(int i = 0; i<Profits.length; i++){
}
for(int i = 0; i<k; i++){
if(q2.size()==0) break;
W += q2.poll().pro;
}
return W;
}
class Point{
int pro;
int cap;
public Point(int p, int c){
this.pro = p;
this.cap = c;
}
}
}
``````

Select all you can select (<=W) from pqCap and add to pqPro. All in pqPro are valid selections! Then select the best one from pqPro.

• I tried this approach using C++, but it doesn't pass the last test with 50000 items

``````class Solution {
public:
struct CompLess {
bool operator() (const pair<int, int>& l, const pair<int, int>& r) {
return l.first > r.first;
}
};

struct CompGreater {
bool operator() (const pair<int, int>& l, const pair<int, int>& r) {
return l.second < r.second;
}
};

int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
priority_queue< pair<int, int>, vector< pair<int, int> >,  CompLess> qcap;
for (int i = 0; i < Profits.size(); ++i) {
qcap.push( make_pair(Capital[i], Profits[i]) );
}

priority_queue< pair<int, int>, vector< pair<int, int> >,  CompGreater> qprof;
for (int i = 0; i < k; ++i) {
while (!qcap.empty() && qcap.top().first <= W) {
qprof.push(qcap.top());
qcap.pop();
}

if (qprof.empty())
break;

W += qprof.top().second;
qprof.pop();
}
return W;
}
};
``````

• A very clean and elegant solution

• Same idea, 41ms

``````public class Solution {
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
if (Profits == null || Profits.length == 0) return 0;
int n = Profits.length;
PriorityQueue<Tuple> q = new PriorityQueue();
for (int i = 0; i < n; i++) {
}
while (!q.isEmpty() && k-- > 0) {
Queue<Tuple> tmp = new ArrayDeque();
while (!q.isEmpty() && q.peek().cap > W) tmp.add(q.poll());
if (q.isEmpty()) return W;
Tuple cur = q.poll();
W += cur.pro;
}
return W;
}

class Tuple implements Comparable<Tuple> {
int pro, cap;
public Tuple(int pro, int cap) {
this.pro = pro;
this.cap = cap;
}

public int compareTo(Tuple that) {
return that.pro - this.pro;
}
}
}
``````

• How do you guys come up with such elegant solutions. Is it all based upon numerous hours of practice or more than that?

• @saiha

Practice makes perfect

• @KirillLykov I met the same problem. Have you solved it yet?

• @xieexiaotuzi nope, I'm passively waiting for someone proposing an alternative. There is also a solution using multimap but it cannot be faster than using two queues (right?).

• @KirillLykov I don't know exactly why multi_map is slower than prority_queue. I think the time complexity is the same. So I need someone's help.

• @xieexiaotuzi the complexity asymptotically is the same, but the constants are different. I guess red-black tree is used for multimap implementation, so it should have a greater constant. For this problem, I first wrote O(N2) solution, it passes all the tests except this N=50000. I wonder what is the referee solution for this problem.

• @KirillLykov Try submitting it again, now that debug mode has been turned off.

• @StefanPochmann thank you, it works.

• AC C++ version. 50-60ms

``````struct CapCmp {
bool operator()(pair<int, int> &a, pair<int, int> &b) {
return a.first > b.first;
}
};
struct ProCmp {
bool operator()(pair<int, int> &a, pair<int, int> &b) {
return a.second < b.second;
}
};
class Solution {
public:
int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
priority_queue<pair<int, int>, vector<pair<int, int>>, CapCmp> cap;
priority_queue<pair<int, int>, vector<pair<int, int>>, ProCmp> pro;
for (int i = 0; i < Profits.size(); ++i) cap.push({ Capital[i], Profits[i] });
while (k--) {
while (cap.size() && cap.top().first <= W) {
pro.push(cap.top());
cap.pop();
}
if (pro.empty()) return W;
W += pro.top().second;
pro.pop();
}
return W;
}
};
``````

• Great solution. I think there are two possible improvements:

• Space: it seems that pqPro doesn't need to store the capital components since it is never used.
• Time: Since we only have maximum k projects to do even though there are N total projects available, I think the time factor logN might be cut down to log(min(N,k)) by maintaining a maximum capped size of priority queue. Imagine when N is huge compared with k, adding all projects to priority queues might be unnecessary. I think this is similar to the classic "get largest k elements " problem, but need to be careful when a project can be discarded.

• great solution with two PriorityQueue.
I think the time-complexity is O( k * N * logN ) ?
N is the input size.

• great solution with two PriorityQueue.
I think the time-complexity is O( k * N * logN ) ?
N is the input size.

The estimate of O(k N logN) is too conservative. The fact is that the algorithm must finish when either k projects are done or all doable projects have been worked, so the factor k is only implicit. The time complexity is actually O(N logN) because each project at most goes through both priority queues once for each.

Actually, I think it might optimize the time with a factor of log(min(N,k)) instead of logN because we don't have to keep more than k elements in the queue. But I need to work out the details. (Considering when N is huge compared with k)

• why cannot I create the priorityqueue same way as you did? My Eclipse just won't compile the code below:

``````(a, b) -> (a[0] - b[0])
``````

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