Hard · Two-Heap Selection
Understand → Visualise → Practice.
Complete at most k projects. A project is available when current capital meets its requirement; profit increases capital. Return maximum final capital.
Sort projects by required capital. Each round, move every newly affordable project into a max-heap by profit, and complete the top one.
Order projects by the capital they need.
Push the profits of all projects with requirement ≤ current capital into a max-heap.
Pop the largest profit and add it to capital; stop early if the heap is empty.
O(n log n + k log n) time and O(n) space.
Choosing the cheapest project first is wrong; among affordable ones, profit is what matters.
Read the full guide first: Heaps and Priority Queues.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.