Почему это работает
- Капитал только растёт, поэтому проект, доступный сейчас, останется доступным. Взять сначала самую большую прибыль ничего не закрывает — это только открывает больше проектов на следующий шаг.
- Проекты отсортированы по нужному капиталу, поэтому i идёт только вперёд: каждый шаг открывает следующие несколько, и каждый проект попадает в кучу один раз.
- В куче лежат все открытые и ещё не взятые проекты, поэтому её верх — лучший выбор шага, как 5, взятая последней здесь.
Сложность
Время O(n log n + k log n): сортировка n проектов, затем каждый не больше одного раза входит в кучу и выходит из неё. Память O(n) на отсортированные проекты и кучу.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗