IPO

Given capital[] and profits[] for n projects, and starting capital w with k projects to pick, maximize capital by doing at most k projects (each can only be done once). Each project requires capital[i] to start and yields profit[i].

Example 1

Input: k=2, w=0, profits=[1,2,3], capital=[0,1,1] → Output: 4

Example 2

Input: k=3, w=0, profits=[1,2,3], capital=[0,1,2] → Output: 6

Solution Approach

Sort projects by capital. Use a max-heap of profits for affordable projects. Greedily pick the most profitable affordable project.

Sort projects by capital requirement.
While k > 0: push all projects with capital <= w into max-heap.
If heap empty: cannot proceed.
Else: pop max profit, add to w, k--.

Java

import java.util.*;

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] = new int[]{capital[i], profits[i]};
        Arrays.sort(projects, (a,b) -> a[0] - b[0]);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int i = 0;
        for (int j = 0; j < k; j++) {
            while (i < n && projects[i][0] <= w) maxHeap.offer(projects[i++][1]);
            if (maxHeap.isEmpty()) break;
            w += maxHeap.poll();
        }
        return w;
    }
}

Time Complexity: O(N log N + k log N)
Space Complexity: O(N)