IPO

502.IPO

Heap

Greedy

Sorting

Problem Statement:

Given k projects, initial capital w, and arrays profit and capital where profit[i] and capital[i] represent the profit and capital of the i-th project, find the maximum capital you can have after finishing at most k distinct projects. You can only start a project if you have enough capital.

Example:

Input:

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

→

Output:

4

Algorithm:

1. Use min heap for sorting by capital
2. Use max heap for available projects
3. Pull projects within current capital
4. Choose most profitable available project

Complexity:

Time: O(NlogN) | Space: O(N)

Java Solution:

public int findMaximizedCapital(int k, int w, int[] profit, int[] capital) {
    // Min heap for capital, max heap for profit
    PriorityQueue cQ = new PriorityQueue<>((a,b) -> a.capital - b.capital);
    PriorityQueue pQ = new PriorityQueue<>((a,b) -> b.profit - a.profit);
    
    // Add all projects to capital queue * CAN ALSO JUST SORT AND USE ONE QUEUE
    for (int i = 0; i < profit.length; i++) 
        cQ.add(new Project(profit[i], capital[i]));
    
    while (k > 0) {
        // Move all available projects to profit queue
        while (!cQ.isEmpty() && cQ.peek().capital <= w) 
            pQ.add(cQ.poll());
        
        if (pQ.isEmpty()) break;  // No projects available
        
        w += pQ.poll().profit;  // Take most profitable project
        k--;
    }
    
    return w;
}

class Project {
    int profit;
    int capital;
    
    public Project(int profit, int capital) {
        this.profit = profit;
        this.capital = capital;
    }
}

Python Solution:

def findMaximizedCapital(self, k: int, w: int, 
                           profits: List[int], capital: List[int]) -> int:
    projects = list(zip(capital, profits))
    projects.sort()  # Sort by capital
    i = 0
    heap = []  # Max heap for profits
    
    while k > 0:
        while i < len(projects) and projects[i][0] <= w:
            heapq.heappush(heap, -projects[i][1])  # Negative for max heap
            i += 1
            
        if not heap:
            break
            
        w -= heapq.heappop(heap)  # Add largest profit
        k -= 1
        
    return w

C++ Solution:

class Solution {
public:
    int findMaximizedCapital(int k, int w, 
                            vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vectorint,int>> projects;
        
        for(int i = 0; i < n; i++) {
            projects.push_back({capital[i], profits[i]});
        }
        sort(projects.begin(), projects.end());  // Sort by capital
        
        priority_queue<int> maxProfit;  // Max heap for profits
        int i = 0;
        
        while(k--) {
            while(i < n && projects[i].first <= w) {
                maxProfit.push(projects[i].second);
                i++;
            }
            
            if(maxProfit.empty()) break;
            
            w += maxProfit.top();
            maxProfit.pop();
        }
        
        return w;
    }
};