Show problems as
Classic problem #1642MediumArrayGreedyHeap (Priority Queue)

Furthest Building You Can Reach

Real-world version: Furthest Relay Mast
Tracked in this browser only
Read Furthest Building You Can Reach on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Relay masts stand in a row along a ridge, and masts[i] is the height of mast i in metres. A technician begins at mast 0 and only ever moves to the mast immediately to the right.

Moving from mast i to mast i + 1 is free whenever masts[i + 1] <= masts[i]. When masts[i + 1] > masts[i], that one move has to be paid for in exactly one of two ways:

  • spend masts[i + 1] - masts[i] metres out of the cable metres on the reel, or
  • spend one of the hoists, which covers a rise of any size.

Both supplies are shared across the whole walk, and neither is refunded. Spend them however you like, and return the index of the furthest mast the technician can end up standing on.

Examples

Example 1

Input
masts = [3,6,4,10], cable = 2, hoists = 1
Output
2

Spending the hoist on the 3 metre rise from mast 0 to mast 1 gets the technician there, and mast 1 to mast 2 drops in height so it is free. The rise from mast 2 to mast 3 is 6 metres, with no hoist left and only 2 metres of cable, so mast 2 is the end of the walk.

Example 2

Input
masts = [8,5,5,9,11], cable = 4, hoists = 0
Output
3

The first move drops, the second is level, and both are free. Paying the 4 metre rise into mast 3 empties the reel, and the 2 metre rise into mast 4 then cannot be paid at all.

Example 3

Input
masts = [2,9], cable = 0, hoists = 1
Output
1

The single 7 metre rise is covered by the one hoist, which works for a rise of any size.

Example 4

Input
masts = [7,7,7], cable = 0, hoists = 0
Output
2

Neither move goes up, so both are free and the empty supplies never matter.

Example 5

Input
masts = [1,4,2,20,21], cable = 3, hoists = 1
Output
3

Paying the 3 metre rise into mast 1 with cable and the 18 metre rise into mast 3 with the hoist reaches mast 3. The 1 metre rise into mast 4 is then unpayable, since the reel is empty and the hoist is gone.

Constraints

  • 1 <= masts.length <= 10^5
  • 1 <= masts[i] <= 10^6
  • 0 <= cable <= 10^9
  • 0 <= hoists <= masts.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def furthest_building(masts: list[int], cable: int, hoists: int) -> int:
Java
public int furthestBuilding(int[] masts, int cable, int hoists)

More on the same topics