Heap / Priority Queue
LC #502Hard
IPO
Heap / Priority Queue
AmazonGoogleBloombergProblem
Maximize capital after completing at most k projects. Each project has a required capital and a profit.
heapgreedysorting
Constraints
- ›1 ≤ k ≤ 10⁵
- ›0 ≤ w ≤ 10⁹
- ›n == profits.length == capital.length
- ›1 ≤ n ≤ 10⁵
Example
Input
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]Output
4Why
Start with 0 capital: take project 0 (profit 1) → capital 1. Now take project 2 (profit 3) → capital 4.