---
# System prepended metadata

title: 1642. Furthest Building You Can Reach
tags: [mock interview, 面試]

---

# 1642. Furthest Building You Can Reach

給定一排房子，每棟房子有自己的高度
你初始位置於 index 0，往前移動，若下一棟房子高度較低，可以直接移動過去
你的手上有一些磚塊和一些梯子，梯子可以無限延長，磚塊可以疊起來
若下一棟房子高度較高，可以使用梯子或是磚塊
請問你最遠可以移動到哪一個位置


house = [1, 3, 5, 1, 2]
bricks = 20 #[1, 10] cost 9 bricks
ladder = 3  #[1, 10] cost 1 ladder


pos 18
1. brick, ladder
pos 19 total-b or totalLadder - 1

br = 200000

house = [1,3,5,7,9,100]
gap.  = [ 2 2 2 2 91]
bricks = 10
ladder = 1


gap.  = [ 2 2 2 2 91 10 5 6]
dp.   = [ 2 2 2] -> [2 2 2 2]=8 >6 heappop->2 [2 2 2]

bricks = 6
ladder = 1
```python=

def findFarestPos(house, bricks, ladders):
    # [-1, -5] -> error b-> >0 
    
    # check param
    
    # [3, 2, 1]
    # [1, 2, 3] b=1 l=1
    # [1, 3, 5, 99] b=3 l=1
    # loop house
    maxHeap = []
    curSum = 0
    for i in range(1, len(house)): #N
        # no need bricks or ladder
        if house[i] <= house[i-1]:
            continue
        gap = house[i] - house[i-1] # 2(3-1) 2(5-3) 94(99-5)
        curSum += gap # 2+94
        heappush(maxHeap, -gap)# [-2, -94] #logN
        
        if curSum > bricks: # 96 > 3
            if ladders == 0:
                return i-1
            negMaxGap = heappop(maxHeap) # -2
            curSum += negMaxGap  #2
            ladders -= 1  #0
    return len(house)-1
    
    N = house element numser
    TC O(NlogN)
```

