A runner starts with reserve calories of energy and burns perMile calories per mile. Each checkpoint holds one drink worth a known number of calories. gaps lists the miles from the start to the first checkpoint, between consecutive checkpoints, and from the last checkpoint to the finish, so it has one more entry than drinks.
The runner can take a drink only at a checkpoint already passed, takes the whole drink, and must not run out of energy before reaching the next point. Arriving with exactly zero is fine. Return the fewest drinks that reach the finish, or -1 if it cannot be done.
- With reserve 10, perMile 1, gaps [10,10,10,30,40] and drinks [60,30,30,40] the answer is 2
- Up to 100,000 checkpoints, so aim for O(n log n)
- A
MaxHeap class with push, pop and size is already written for you