Furthest Building You Can Reach LeetCode solution in C++

1
class Solution {
2
 public:
3
  int furthestBuilding(vector<int> &heights, int bricks, int ladders) {
4
    // Priority Queue for storing the bricks used in each step in decreasing
5
    // order (Max at top)
6
    priority_queue<int> maxB;
7

8
    int i = 0, diff = 0;                       // i is used for storing the position and diff for
9
                                               // storing difference.
10
    for (i = 0; i < heights.size() - 1; i++) { // go till before the last building.
11

12
      // difference of the height of corresponding buildings
13
      diff = heights[i + 1] - heights[i];
14

15
      // If next building is equal or samaller than current then go to next
16
      // building.
17
      if (diff <= 0) {
18
        continue;
19
      }
20

21
      bricks -= diff;  // taking the bricks needed for going to next building.
22
      maxB.push(diff); // adding the number of bricks used in priority queue.
23

24
      // if bricks become negetive then there were not enough bricks. So add a
25
      // ladder in place of the step where most bricks were used.
26
      if (bricks < 0) {
27
        bricks += maxB.top(); // taking back bricks from that step
28
        maxB.pop();           // As max bricks were removed so pop
29
        ladders--;            // 1 ladder used
30
      }
31

32
      // if ladder is negetive then the ladder was not provided to go to next
33
      // building. So we can't proceed.
34
      if (ladders < 0) break;
35
    }
36

37
    // return the present position.
38
    return i;
39
  }
40
};