← Back to Heap Pattern

📚 IPO (Initial Public Offering) – Java Cheat Sheet

📌 What Is It?

The IPO problem involves selecting projects to maximize capital given limited initial resources. Each project has a profit and a capital requirement.

• Select projects that maximize profit
• Use a min-heap and max-heap to manage capital and profits
• Handle constraints like limited initial capital

🧱 Pattern Template

class Solution {
    // Helper class to store project profit and capital
    class Pair {
        int pro; // Profit of the project
        int cap; // Capital required to start the project

        Pair(int pro, int cap) {
            this.pro = pro;
            this.cap = cap;
        }
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length; // Number of projects
        Pair[] projects = new Pair[n]; // Array to store all projects

        // Step 1: Create Pair objects for each project
        for (int i = 0; i < n; i++) {
            projects[i] = new Pair(profits[i], capital[i]);
        }

        // Step 2: Sort projects by their capital requirements in ascending order
        Arrays.sort(projects, (a, b) -> a.cap - b.cap);

        // Step 3: Use a max-heap to store projects based on their profit
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> b.pro - a.pro);

        int idx = 0; // Pointer to iterate through the sorted projects array

        // Step 4: Select up to 'k' projects
        while (k-- > 0) {
            // Add all projects that can be started with the current capital to the max-heap
            while (idx < n && projects[idx].cap <= w) {
                pq.offer(projects[idx++]);
            }

            // If no projects can be started, break the loop
            if (pq.isEmpty()) {
                break;
            }

            // Step 5: Select the most profitable project and update the available capital
            w += pq.poll().pro;
        }

        // Step 6: Return the final capital after selecting up to 'k' projects
        return w;
    }
}

📊 Time Complexity

• Sorting Projects: Sorting the `projects` array by capital takes O(n log n), where n is the number of projects.
• Heap Operations:
  • Each project is added to the max-heap at most once. Adding to or removing from the heap takes O(log n).
  • In the worst case, all n projects are added to the heap, and the loop runs k times. Thus, heap operations take O(k log n).
• Overall Complexity: The total time complexity is O(n log n + k log n).

✅ Use Cases

• Maximizing profit with limited resources
• Scheduling problems with constraints
• Dynamic selection of tasks based on priority

📘 Common LeetCode Problems

• 502. IPO [Hard] Heap

🧪 Example: IPO

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: 
- Select project 0 (profit = 1, capital = 0), updated capital = 1.
- Select project 2 (profit = 3, capital = 1), updated capital = 4.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to track projects by capital
• Use a max-heap to select the most profitable project
• Edge cases: no projects can be started, or k is greater than the number of projects