---
# System prepended metadata

title: 0502. IPO
tags: [Leetcode, Priority Queue, Hard, Greedy]

---

# 0502. IPO
###### tags: `Leetcode` `Hard` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/ipo/
## 思路 $O(NlogN)$ $O(N)$
建一个priorityQueue pool，然后把所有capital profits pair放进去，并且按照capital从小到大排 这样才能做到给定一个w，按顺序找到所有满足capital<=w的pair
再建一个priorityQueue maxProfit，然后把所有符合条件，也就是capital<=w的pairs放进去，然后按照profit从大到小排，保证我们能找到所有符合条件的pairs里面带来最大收益的那个
## Code
```java=
class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        Queue<int[]> pool = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        Queue<int[]> maxProfit = new PriorityQueue<>((a,b)->(b[1]-a[1]));
        for(int i=0; i<profits.length; i++){
            pool.add(new int[]{capital[i], profits[i]});
        }
        
        int num = 0;
        for(int i=0; i<k; i++){
            while(!pool.isEmpty() && pool.peek()[0]<=w){
                maxProfit.add(pool.poll());
            }    
            if(maxProfit.isEmpty()) break;
            w += maxProfit.peek()[1];
            maxProfit.poll();
        }
        return w;
    }
}
```