> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/heaps-and-priority-queue/1642.-furthest-building-you-can-reach.md).

# 1642. Furthest Building You Can Reach

## Problem Statement

<br>

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.*

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/27/q4.gif)

<pre><code><strong>Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
</strong><strong>Output: 4
</strong><strong>Explanation: Starting at building 0, you can follow these steps:
</strong>- 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 &#x3C; 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 &#x3C; 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
</code></pre>

**Example 2:**

<pre><code><strong>Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
</strong><strong>Output: 7
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: heights = [14,3,19,3], bricks = 17, ladders = 0
</strong><strong>Output: 3
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= heights.length <= 105`
* `1 <= heights[i] <= 106`
* `0 <= bricks <= 109`
* `0 <= ladders <= heights.length`

## Intuition

```
Approach: 
Dp wont work here,
We try a Greedy approach

Till every index, find for ladder the maximum jumps and for minimum jumps 
We satisfy those with bricks

We use priority queue for this and when the ladder count exceed in pq
We satisfy with bricks
```

### Links

<https://leetcode.com/problems/furthest-building-you-can-reach/description/?envType=daily-question&envId=2024-02-17>

### Video Links

<https://www.youtube.com/watch?v=35Z60cfjgKA&ab_channel=AryanMittal>

### Approach 1:

```
NlogN Greedy
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int furthestBuilding(vector<int>& arr, int bricks, int ladders) {
        int n = arr.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i=1; i<arr.size(); i++){
            int diff = arr[i] - arr[i-1];
            if(diff < 0)
                continue;

            if(pq.size() < ladders)
                pq.push(diff);
            else{
                pq.push(diff);
                int top = pq.top();
                pq.pop();
                if(bricks >= top)
                    bricks -= top;
                else
                    return i-1;
            }
        } 

        return n-1;

    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###