502. IPO

first sort the capital (use PriorityQueue, save capital and profit info, sort by asc for capital),

find the smallest boundary <= w, then you can start a new project,

but you should choose the maximum profits of projects you can start

so PriorityQueue sort with profit by desc is the rescue.

time: O(nlogn)

space:O(n)

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // if capital[i] <= w, minimum capital , can start this project, get profits[i]
        // c = [0, 1, 1], w = 0, get profit[0] = 1, w+= profit[0]
        // c = [0, 1, 1], w = 1, profits = [1,2,3] => so should sort profits desc
        
        PriorityQueue<int[]> cap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pro = new PriorityQueue<>((a, b) -> b - a);
        
        for (int i = 0; i < capital.length; i++) {
            cap.offer(new int[]{capital[i], profits[i]});
        }
        
        for (int i = 0; i < k; i++) {
            while (!cap.isEmpty() && w >= cap.peek()[0]) {
                pro.offer(cap.poll()[1]);
            }
            if (pro.isEmpty()) {
                break;
            }
            w += pro.poll();
        }
        return w;
    }
}