This type of problem is different from the simple extreme value problems in two folds:

1. It need to be an extreme value;
2. It need to to satisfy a few other conditions. Simply sorting the array could give you extreme value overall but without satisfying the second conditions. One approach is to sort the array by the second condition and then by the extreme value.

• Leetcode - 502

Firstly, this could be solved by Greedy approach:

1. For all the projects that satisfy capital <= w, select the most profitable one.
2. Add the profit to capital, remove this project from available projects.

The problem now is how to select the most profitable project with a condition capital <= w. We could sort all the project by profit, but can’t gurantee the capital condition is satisfied.

Brutal force

Scan all projects, and find the max profit with capital <= w; This takes linear time for each selection.

Sort

Keep in mind that the current capital is increasing after every project selection. We could use this to add only the projects that satisfy the new capital condition.

1. Initial a max heap with capital;
2. Sort the projects by capital;
3. Put the projects that satisfy initial capital condition to the max heap;
4. For every selection, poll a project from the max heap, and increment current capital.
5. Put all projects that satisfy the new capital into max heap;

Every project need to be visited once only, so the time complexity would be O(k+n), where k is the given k, and n is the length of projects.

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        
        //Greedy method
        PriorityQueue<int[]> pq = new PriorityQueue<>((x,y)-> -1*Integer.compare(x[1],y[1]));
        
        int[][] projects = new int[profits.length][2];
        
        for (int i = 0; i < profits.length; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }      
        
        Arrays.sort(projects, (x,y)->Integer.compare(x[0], y[0]) );
        int id = 0;
        while (id < projects.length && projects[id][0] <= w) {
                pq.add(projects[id++]);
        }
        
        while (k > 0) {
            if (pq.isEmpty()) return w;
            int[] maxProfit = pq.poll();          

            w += maxProfit[1];            
            while (id < projects.length && projects[id][0] <= w) {
                pq.add(projects[id++]);
            }            
            k--;
        }
        
        return w;
    }