# 1642. Furthest Building You Can Reach
Young

{%hackmd theme-dark %}

h = [2, 3, 5, 1]
brick = 20 2->3:1 3->5:2
ladder = 3. 1->19999:1

i brick ladder

find max index of dfs(brick - h[i+1], ladder), dfs(brick, ladder-1)

b=6 l=1
house = [1,3,6,8,10,100]
[ b.l b b ^.]
1 3 6 100 102 104
gap. = [ 2+3+94 2 2 90]

int maxDistance(vecotr<int> &height, int bricks, int ladders) {
    
    if (bricks < 0 || ladder < 0) {
        return -1;
    }
    
    if (height.size() == 1) {
        return 1;
    }
    // h: [1, 3, 6, 8, 10, 100], brick 10, 1 ladder
    // maxHeap 3,2,2,2 brick 1, 1 ladder
    // [1, 2, 3] b=1 l=1
    // [1, 3, 5, 99] b=3 l=1

    // 1, 3, 5, 99, b=3, l=1
    // 3: b:1, l:1 max: 2
    // 5: b:3, l:0 max:
    // 99 b:1, l:0 max: 2
    priority_queue<vector<int>> maxHeap;
    int i = 1;
    while (i < height.size() && bricks > 0 && ladders != 0; i++) {
        if (height[i] >= height[i-1]) {
            i++;
            continue;
        }
        
        bricks -= height[i] - height[i-1];
        if (bricks < 0) {
            if (!maxHeap.empty() && ladder > 0) {
                bricks += maxHeap.top();
                maxHeap.pop();
                ladders--;
            } else if (ladder > 0) {
                ladders--;
                i++;
            } else {
                return i-1;
            }
        } else {
            maxHeap.push(height[i] - height[i-1]);
            i++;
        }
    }
    
    return i-1;
}

###### tags: `mock interview` `面試`