262. IPO

At each of the k rounds, among all projects you can currently afford, always take the one with the highest profit. Sort projects by required capital so you can unlock newly-affordable ones as your capital grows, and keep affordable profits in a max-heap.

Idea

Because completing a project only ever increases your capital, being greedy is optimal: at each step do the most profitable project you can currently afford. As capital grows, more projects become affordable, so we unlock them progressively.

Sort projects by required capital. A max-heap holds the profits of every project whose capital requirement is <= w. Each round: unlock all newly-affordable projects into the heap, then take the top (highest profit) and add it to w.

Algorithm

1. Pair and sort projects by capital ascending.
2. Repeat up to k times:
   • Push into a max-heap the profit of every remaining project with capital <= w (advance a pointer).
   • If the heap is empty, no affordable project remains → stop.
   • Pop the max profit and add it to w.
3. Return w.

Worked example: k=2, w=0, profits=[1,2,3], capital=[0,1,1]

Sorted by capital: (0,1), (1,2), (1,3).

• Round 1: affordable with w=0 → project (0,1). Heap {1}. Take 1 → w=1.
• Round 2: affordable with w=1 → (1,2),(1,3). Heap {2,3}. Take 3 → w=4.

Final capital: 4.

Complexity

• Time: O(n log n) — sort plus heap operations.
• Space: O(n) for the heap.

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> available = new PriorityQueue<>(Collections.reverseOrder());
        int i = 0;
        for (int round = 0; round < k; round++) {
            while (i < n && projects[i][0] <= w) {
                available.offer(projects[i][1]);
                i++;
            }
            if (available.isEmpty()) {
                break;
            }
            w += available.poll();
        }
        return w;
    }
}