IPO
IPO is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.
Problem statement
You are given a collection of projects. Project i requires capital[i] units of capital to begin and produces profits[i] units of profit when completed. The two arrays describe matching projects, so project i uses the values at index i in both arrays; each project may be completed at most once.
You begin with w units of capital. At any point, you may choose a not-yet-completed project whose required capital is no greater than your current capital. Completing it immediately increases your capital by its profit. You may complete at most k projects, and may stop earlier if no remaining project is affordable.
Implement findMaximizedCapital in the Solution class. Return the greatest capital amount that can be held after choosing up to k projects.
Example 1:
Input: k = 2, w = 3, profits = [6,4,10,2], capital = [3,5,3,9] Output: 19 Explanation: Both projects requiring 3 capital are initially available. Choosing the project with profit 10 raises the capital to 13, after which choosing the project with profit 6 produces a final capital of 19.
Example 2:
Input: k = 3, w = 1, profits = [2,11,7,20], capital = [1,8,4,15] Output: 3 Explanation: The project requiring 1 capital can be completed, raising the total to 3. Neither remaining project is then affordable, so no further project can be chosen.
Example 3:
Input: k = 4, w = 6, profits = [3,12,5,9,1], capital = [2,10,7,6,20] Output: 35 Explanation: Choose the project with profit 9 first, then the projects with profits 12, 5, and 3 become affordable in sequence. The capital increases from 6 to 35.
Constraints:
- 1 <= k <= 10^5 - 0 <= w <= 10^9 - 1 <= profits.length = capital.length <= 10^5 - 0 <= profits[i] <= 10^4 for every valid index i - 0 <= capital[i] <= 10^9 for every valid index i - The returned answer fits in a 32-bit signed integer.
Topics and companies
Topics: Heap, Greedy, Sorting, Array.
How to practise IPO on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n + k log n), where n is the number of projects. time and O(n) space.
Open IPO in the code editor, or read the IPO editorial for a worked solution with its approach and complexity analysis.
Where IPO sits in the DSA pattern sheet
- Heap (Priority Queue) Patterns pattern guide
- Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to IPO
Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:
- Furthest Building You Can Reach — Medium, same subpattern
- Longest Happy String — Medium, same subpattern
- Maximum Average Pass Ratio — Medium, same subpattern
- Meeting Rooms II — Medium, same subpattern
- Meeting Rooms III — Hard, same subpattern
- Minimum Cost to Hire K Workers — Hard, same subpattern