O((K + N)logN) One PriorityQueue Java Solution with Comments (60ms)

• ``````public class Solution {

public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
if (Profits == null || Capital == null) {
return 0;
}
ArrayList<Pair> projects = new ArrayList<>();
int n = Profits.length;
for (int i = 0; i < n; i++) {
}
// sort all the project with capital ascending order
// make it convenient to check all the projects that satisfy current capital constrain
Collections.sort(projects, new Comparator<Pair>() {
public int compare(Pair p1, Pair p2) {
int diff = p1.cap - p2.cap;
if (diff == 0) {
diff = p2.prf - p1.prf;
}
return diff;
}
});

// maxheap : always garantee that the top of pq has maximual profit
PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {
public int compare(Pair p1, Pair p2) {
int diff = p2.prf - p1.prf;
if (diff == 0) {
diff = p1.cap - p1.cap;
}
return diff;
}
});

// the potential project we start to look at
int i = 0;
// loop for k round
int maxCapital = W;
for (int j = 0; j < k; j++) {
// initialization for each round
// put all the projects that satisfy current capital constrain into PQ
for (; i < n; i++) {
if (projects.get(i).cap <= maxCapital) {
} else {
break;
}
}
// the top of PQ would be our best choice of this round
if (!pq.isEmpty()) {
maxCapital += pq.poll().prf;
}
}
return maxCapital;
}
}

class Pair {
int prf;
int cap;
public Pair(int prf, int cap) {
this.prf = prf;
this.cap = cap;
}
}
``````

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