Leetcode 502 - IPO [15/6/24]

Time Taken: ~25 mins
Tag: LeetCode Hard
Basic ideas: (Greedy, Heap)
We need to keep track of:
Group 1 (tracked in “pq”) - projects that we are able to take on with the current budget, w. (project’s capital needed less than or equal w)
Group 2 (tracked in “minHeap”) - projects that we are not able to take on. (project’s capital needed greater than w)
As long as we still are within limits on the number of projects taken (k greater than 0) and we have eligible projects (!pq.empty()):
Greedily take the top project from pq, since pq is stored as a maxHeap, where the profits are stored in descending order.
Small note: Capital actually does not matter within the “pq”, as profits are the pure profits that we obtain and can be added to w (our budget) after taking on a project
Now that w has increased, we add newly eligible projects, where project’s capital needed less than or equal w, from “minHeap” into “pq”
Return w.