Potions - Problem Statement

Drink potions in order. Each gives or takes health. Never go below $0$. Find the largest potions drunk. Greedy with regret: drink each potion. If health goes negative, 'un-drink' the worst positive potion. Use max-heap of potion effects. When negative, pop max positive effect and restore health. This is the regret trick again. The heap tracks regrettable decisions. Time: $O(n \log n)$.

Time complexity: $O(n \log n)$.

Space complexity: $O(n)$. The regret trick appears again. When forced into a bad state, undo the worst previous decision.