Furthest Building You Can Reach

Buildings stand in a row with heights[i]. You start on building 0 and move to the next building each step. If the next building is not higher, you just walk. If it is higher, you must climb using bricks (the number of bricks equals the height difference) or one ladder (any height, ladders are used up). Return the index of the furthest building you can reach.

For heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5 and ladders = 1 the answer is 4.

The starter code sorts all the climbs again for each building. It is correct but too slow for many buildings.

Examples

Example 1

Input:

furthest_building([4, 2, 7, 6, 9, 14, 12], 5, 1)

Output:

4

Example 2

Input:

furthest_building([4, 12, 2, 7, 3, 18, 20, 3, 19], 10, 2)

Output:

7

Constraints

• 1 <= len(heights) <= 100000
• 1 <= heights[i] <= 10**6
• 0 <= bricks <= 10**9
• 0 <= ladders <= len(heights)