Problem #502: IPO

Intuition & Strategy Breakdown

Use a min-heap for projects sorted by capital requirement and max-heap for affordable projects sorted by profit. Greedily pick max profit project K times.

Python Solution

import heapq

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
        n = len(profits)
        projects = sorted(zip(capital, profits))
        
        max_heap = []
        i = 0
        
        for _ in range(k):
            while i < n and projects[i][0] <= w:
                heapq.heappush(max_heap, -projects[i][1])
                i += 1
            
            if not max_heap:
                break
                
            w += -heapq.heappop(max_heap)
            
        return w

Java Solution

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][0] = capital[i];
            projects[i][1] = profits[i];
        }
        
        Arrays.sort(projects, (a, b) -> Integer.compare(a[0], b[0]));
        
        PriorityQueue 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]);
                i++;
            }
            
            if (maxHeap.isEmpty()) {
                break;
            }
            
            w += maxHeap.poll();
        }
        
        return w;
    }
}