Why it works
- Capital only grows, so a project we can afford now stays affordable. Taking the largest profit first never closes a door: it only opens more projects for the next round.
- The projects are sorted by the capital they need, so i only moves forward: each round unlocks the next few, and every project enters the heap once.
- The heap keeps every unlocked project that is not taken yet, so its top is the best choice of the round, like the 5 taken last here.
Complexity
Time O(n log n + k log n): sorting n projects, then each enters and leaves the heap at most once. Memory O(n) for the sorted projects and the heap.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗