Ladders and Bricks Across the Rooftops

Medium

You are running across the rooftops of a row of buildings. Roof heights are given in roofs; you start on roof 0 and can only step to the next roof each time. - If the next roof is not higher than the current one, the step is free. - If it is higher by d, you must either place one ladder or lay down d bricks. You have bricks bricks and ladders ladders, and each can be used only once. Spend them as wisely as possible and return the index of the farthest roof you can reach.

Example 1

roofs=[3, 8, 6, 10, 11, 4, 9], bricks=4, ladders=1 → 3

Roof 0 to 1 is a climb of 5, so the ladder goes there. Roof 1 to 2 goes down. Roof 2 to 3 is a climb of 4, which uses all 4 bricks. Roof 3 to 4 is a climb of 1 with nothing left, so roof 3 is as far as you get. Giving the ladder to the climb of 4 instead fails even sooner, at the climb of 5.

Example 2

roofs=[9, 7, 7, 2], bricks=0, ladders=0 → 3

There are no climbs at all, so you reach the last roof, index 3.

Example 3

roofs=[1, 4, 2, 7, 5, 6], bricks=3, ladders=1 → 4

The climbs are 3, 5 and 1. The ladder is best spent on the 5 and the 3 bricks cover the 3. Nothing is left for the final climb of 1, so roof 4 is the last one you reach.

Constraints

1 ≤ len(roofs) ≤ 10⁵
1 ≤ roofs[i] ≤ 10⁶
0 ≤ bricks ≤ 10⁹
0 ≤ ladders ≤ len(roofs)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Heap (Priority Queue)