BiruLyu
6/21/2017 - 10:13 PM

## 502. IPO(one heap).java

``````public class Solution {
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<int[]> candidates = new PriorityQueue<int[]>( new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});

PriorityQueue<int[]> maxHeap = new PriorityQueue<int[]> (new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return b[1] - a[1];
}
});

for (int i = 0; i < Profits.length; i++) {
candidates.offer(new int[] {Capital[i], Profits[i]});
}

for (int i = 0; i < k; i++) {
while (!candidates.isEmpty() && W >= candidates.peek()[0]) {
maxHeap.offer(candidates.poll());
}
if (maxHeap.isEmpty()) break;
W += maxHeap.poll()[1];
}
return W;
}
}``````
``````public class Solution {
class Pair {
int profit;
int capital;
public Pair (int profit, int capital) {
this.profit = profit;
this.capital = capital;
}
}
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<Pair> heap = new PriorityQueue<Pair>(new Comparator<Pair>() {
public int compare(Pair p1, Pair p2) {
if (p1.profit == p2.profit) return p1.capital - p2.capital;
return p2.profit - p1.profit;
}
});
for (int i = 0; i < Capital.length; i++) {
}
for (int i = 0; i < k; i++) {
List<Pair> tmp = new ArrayList<Pair>();
while (!heap.isEmpty() && heap.peek().capital > W) {