1642. Furthest Building You Can Reach #

Problem #

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.
If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

1 <= heights.length <= 10^5
1 <= heights[i] <= 10^6
0 <= bricks <= 10^9
0 <= ladders <= heights.length

Problem Summary #

You are given an integer array heights, representing the heights of buildings. There are also some bricks and ladders. You start your journey from building 0 and keep moving to later buildings, possibly using bricks or ladders along the way. When moving from building i to building i+1 (0-indexed):

If the current building’s height is greater than or equal to the next building’s height, no ladder or bricks are needed.
If the current building’s height is less than the next building’s height, you can use one ladder or (h[i+1] - h[i]) bricks.

Return the index of the furthest building you can reach (0-indexed) if you use the given ladders and bricks optimally.

Solution Approach #

For this problem, you might think of a greedy algorithm. Ladders are very powerful and can be infinitely long, so ladders should be used to cross the tallest buildings. When encountering a height difference that is not the largest, use bricks first. However, this greedy approach is incorrect. For example, for the data set [1, 5, 1, 2, 3, 4, 10000], there is 1 ladder and 4 bricks. The largest gap is between 10000 and 4, so the greedy choice is to use the ladder there. But the bricks are not enough to let us reach the last two buildings. The greedy result is 3, while the correct result is 5: use the ladder first, then use bricks to pass buildings 3, 4, and 5.
The mistake in the above greedy solution is that it does not use “dynamic” greediness. Ladders should be used for the highest climbs among the buildings that can be climbed over. Thus, a priority queue naturally comes to mind. Maintain a min-heap with length equal to the number of ladders. When the number of elements in the queue exceeds the number of ladders, pop the smallest value at the front of the queue, and use bricks to cover this height difference between buildings. When all bricks are used up, that is the furthest building index that can be reached.

Code #

package leetcode

import (
	"container/heap"
)

func furthestBuilding(heights []int, bricks int, ladder int) int {
	usedLadder := &heightDiffPQ{}
	for i := 1; i < len(heights); i++ {
		needbricks := heights[i] - heights[i-1]
		if needbricks < 0 {
			continue
		}
		if ladder > 0 {
			heap.Push(usedLadder, needbricks)
			ladder--
		} else {
			if len(*usedLadder) > 0 && needbricks > (*usedLadder)[0] {
				needbricks, (*usedLadder)[0] = (*usedLadder)[0], needbricks
				heap.Fix(usedLadder, 0)
			}
			if bricks -= needbricks; bricks < 0 {
				return i - 1
			}
		}
	}
	return len(heights) - 1
}

type heightDiffPQ []int

func (pq heightDiffPQ) Len() int            { return len(pq) }
func (pq heightDiffPQ) Less(i, j int) bool  { return pq[i] < pq[j] }
func (pq heightDiffPQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *heightDiffPQ) Push(x interface{}) { *pq = append(*pq, x.(int)) }
func (pq *heightDiffPQ) Pop() interface{} {
	x := (*pq)[len(*pq)-1]
	*pq = (*pq)[:len(*pq)-1]
	return x
}