Ladders or bricks
Walk along buildings of different heights, climbing each rise with bricks or a ladder, and find the furthest you can get, by giving ladders to the biggest rises. About 20 minutes.
Ladders for the biggest rises
Walking from building to building, a drop or flat step costs nothing. A rise needs bricks equal to the rise, or one ladder, which covers any height. You have a number of bricks and ladders, and want to get as far as possible.
The best use of ladders is on the biggest rises, since that saves the most bricks. But you do not know in advance which rises will be the biggest.
d = heights[i + 1] - heights[i]
if d > 0:
heapq.heappush(heap, d)3 to 6 is a rise of 3. Give it the ladder.
Decide with regret
Keep a min-heap of the rises that currently hold ladders. For each new rise, give it a ladder: push it. If that uses more than the ladders you own, take the smallest rise out of the heap and pay for it with bricks instead.
If the bricks become negative, you cannot afford the step: the answer is the building you are on. If you get through every step, the answer is the last building.
if len(heap) > limit:
removed = heapq.heappop(heap)Why pay with bricks for the smallest rise among those holding ladders?
- AIt costs the fewest bricks, so the ladders stay on the biggest rises
- BIt costs the most bricks
- CIt is the earliest rise
Show the answer
It costs the fewest bricks, so the ladders stay on the biggest rises. A ladder saves more bricks on a bigger rise.
Furthest building you can reach
heights holds the heights of buildings in a row, and you have some bricks and some ladders. You start on building 0 and walk to the next building each step. If the next building is not taller, the step is free. If it is taller by d, you must spend d bricks or one ladder. Return the index of the furthest building you can reach.
heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1 → 4
1 ≤ length of heights ≤ 100,000 · 1 ≤ heights[i] ≤ 1,000,000 · 0 ≤ bricks ≤ 1,000,000,000 · 0 ≤ ladders ≤ length of heights