DSA · Greedy / Heap · #90
IPO
Module 68 · difficulty 4/5·⏱ 30:00starts on first keystroke
Before an IPO, a project house wants to maximize its total capital by completing at most `k` distinct projects. You start with `w` capital. Project `i` has a pure profit `profits[i]` and requires a minimum capital `capital[i]` to start. When you finish a project, its profit is added to your capital. Each project can be done at most once. Implement `findMaximizedCapital(k, w, profits, capital)` that returns the maximum capital you can accumulate after finishing at most `k` projects.
Examples
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]→4— Start with w=0, only project 0 is affordable -> capital 1. Now projects 1 and 2 are affordable; pick project 2 (profit 3) -> capital 4.k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]→6— Do all three in order: 0->1, 1->3, 2->6.k = 1, w = 2, profits = [1,2,3], capital = [1,1,2]→5— All three affordable; pick the largest profit 3 -> capital 5.
Constraints
- · 1 <= k <= 10^5
- · 0 <= w <= 10^9
- · profits.length == capital.length == n
- · 1 <= n <= 10^5
- · 0 <= profits[i] <= 10^4
- · 0 <= capital[i] <= 10^9
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.