https://leetcode.com/problems/furthest-building-you-can-reach/ from Google

Thinking process:

Check the constraint first. Looks like we need to do this in O(nlogn) time.

Looking into the problem, basically we only need to care about the height increasing case. For example, if our heights=[0,8,10,12,14,16,18], then the diff array will be

8,2,2,2,2,2

Now, let’s say we have 10 bricks and 1 ladder. It’s obvious we’ll not use our bricks to cover the first 8 diff, so the ladder should be used to cover the biggest diff in any case. But how do we know we need to use ladder for the first 8 rather than some diff later? We don’t, but we can try to keep as many as diff in bricks, and if the diff sum is more than our bricks, we have no choice but pick the biggest diff and replace it by ladder. Then we free up some space for bricks.

In this example, we’ll

8 -> use bricks: [8], ladder: 1
2 -> use bricks: [2,8], ladder: 1
2 -> can't use bricks, but we have ladder, so we replace 8 with ladder. 
Then we can use bricks to cover more: [2,2], ladder: 0

...and so on

Below is the code.

 1class Solution {
 2public:
 3    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
 4        int N = heights.size();
 5        if (N == 1) return 1;
 6        priority_queue<int> pq;
 7        int i = 1;
 8        int s = 0;
 9        for (; i<N; i++) {
10            int diff = max(0, heights[i] - heights[i-1]);
11            pq.push(diff);
12            s += diff;
13            if (s > bricks) {
14                int x = pq.top(); pq.pop();
15                s -= x;
16                ladders--;
17            }
18            if (ladders < 0) break;
19        }
20        return i-1;
21    }
22};