A runner crosses a row of rooftops with heights heights, moving from roof i to roof i + 1. Dropping down or staying level costs nothing. Climbing up by d = heights[i+1] - heights[i] > 0 requires either d bricks or one ladder (a ladder covers any climb, whatever its height). The runner starts with bricks bricks and ladders ladders.
Return the index of the furthest roof the runner can reach (the last index if the whole row is crossable).
Examples
Input: heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1
Output: 4
Explanation: 4->2 free; 2->7 (climb 5) use the ladder; 7->6 free; 6->9 (climb 3) use 3 bricks;
9->14 (climb 5) needs 5 bricks but only 2 remain, so the runner stops on roof 4.
Input: heights = [1, 5, 1, 2, 3, 4, 10000], bricks = 4, ladders = 1
Output: 5
Explanation: reaching the last roof would need the ladder on the climb of 9996 plus
4 + 1 + 1 + 1 = 7 bricks, more than the 4 available. Using the ladder on the climb
of 4 and three bricks on the small climbs reaches roof 5.
Constraints
1 <= len(heights) <= 10**5,1 <= heights[i] <= 10**60 <= bricks <= 10**9,0 <= ladders <= len(heights)- Target complexity: O(n log L) where
Lis the number of ladders.
Goals
- Decide lazily which climbs get the scarce resource
- Keep the largest climbs in a heap bounded by the number of ladders
- Detect the exact index where the resources run out