502. IPO

Array Greedy Sorting Heap (Priority Queue)

Time: O(n log n)

Space: O(n)

Intuition

Greedily pick the most profitable project you can afford. Use a min-heap for capital requirements and a max-heap for profits of affordable projects.

Algorithm

1Sort projects by capital required.
2Use pointer to track which projects are now affordable as capital grows.
3For each of k rounds: push all newly affordable projects' profits to max-heap. Pop max profit. Add to capital.

Common Pitfalls

•If max-heap is empty (no affordable projects), break early — can't make more money.

502.cs

// Approach: Min-heap by capital releases affordable projects to a max-heap
// by profit; greedily pick the best available project k times.
// Time: O(n log n) Space: O(n)

public class Solution {
    public int FindMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        var pqMin = new PriorityQueue<IPO, IPO>(Comparer<IPO>.Create((a, b) => a.capital.CompareTo(b.capital)));
        var pqMax = new PriorityQueue<IPO, IPO>(Comparer<IPO>.Create((a, b) => b.profit.CompareTo(a.profit)));

        for(int i = 0; i < capital.Length; i++)
        {
            var ipo = new IPO(profits[i], capital[i]);
            pqMin.Enqueue(ipo, ipo);
        }

        while(k-- > 0)
        {
            while(pqMin.Count > 0 && pqMin.Peek().capital <= w)
            {
                pqMax.Enqueue(pqMin.Peek(), pqMin.Peek());
                pqMin.Dequeue();
            }

            if(pqMax.Count == 0)
                break;

            w += pqMax.Dequeue().profit;
        }

        return w;
    }
}

public class IPO
{
    public int profit;
    public int capital;

    public IPO(int pro, int cap)
    {
        this.profit = pro;
        this.capital = cap;
    }
}

Was this solution helpful?