IPO

Сложная№502лучший из доступных

Вначале капитал w, и можно выполнить не больше k проектов, один за другим. Проекту n для старта нужен капитал capital[n], а после него капитал растёт на profits[n]; ничего не тратится. Нужно вернуть наибольший капитал, с которым можно закончить. Наш пример: k = 3, w = 1, profits [4, 2, 5, 1, 3, 1], capital [3, 0, 6, 1, 2, 4] — ответ 12: проекты с прибылью 2, 4 и 5, в таком порядке.

502 IPOРазбор · 1×

Пример: k = 3, w = 1, profits [4, 2, 5, 1, 3, 1], capital [3, 0, 6, 1, 2, 4]. Сверху — проекты, отсортированные по нужному капиталу; ниже — макс-куча доступных прибылей.

capitalprofit012346213415w = 1макс-кучаприбылей
закрыт: нужно больше wтолько что положили или взялив куче, можно начатькорень: лучшая доступная прибыльсделан, прибыль добавлена к w

Сортируем проекты по нужному капиталу: 0, 1, 2, 3, 4, 6

01/35
сначала · назад · пуск · шаг
Скорость
1function findMaximizedCapital(k, w, profits, capital):
2 projects = pairs (capital, profit), sorted by capital
3 heap = empty max-heap // profits we can afford
4 i = 0
5 repeat k times:
6 while i < len(projects) and projects[i].capital <= w:
7 push projects[i].profit into heap
8 i = i + 1
9 if heap is empty:
10 return w
11 w = w + pop max from heap
12 return w
состояние
w
1
i
–
heap
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Капитал только растёт, поэтому проект, доступный сейчас, останется доступным. Взять сначала самую большую прибыль ничего не закрывает — это только открывает больше проектов на следующий шаг.
  2. Проекты отсортированы по нужному капиталу, поэтому i идёт только вперёд: каждый шаг открывает следующие несколько, и каждый проект попадает в кучу один раз.
  3. В куче лежат все открытые и ещё не взятые проекты, поэтому её верх — лучший выбор шага, как 5, взятая последней здесь.

Сложность

Время O(n log n + k log n): сортировка n проектов, затем каждый не больше одного раза входит в кучу и выходит из неё. Память O(n) на отсортированные проекты и кучу.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.