<p>You are given an integer array <code>heights</code> representing the heights of buildings, some <code>bricks</code>, and some <code>ladders</code>.</p>

<p>You start your journey from building <code>0</code> and move to the next building by possibly using bricks or ladders.</p>

<p>While moving from building <code>i</code> to building <code>i+1</code> (<strong>0-indexed</strong>),</p>

<ul>
	<li>If the current building&#39;s height is <strong>greater than or equal</strong> to the next building&#39;s height, you do <strong>not</strong> need a ladder or bricks.</li>
	<li>If the current building&#39;s height is <b>less than</b> the next building&#39;s height, you can either use <strong>one ladder</strong> or <code>(h[i+1] - h[i])</code> <strong>bricks</strong>.</li>
</ul>

<p><em>Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/27/q4.gif" style="width: 562px; height: 561px;" />
<pre>
<strong>Input:</strong> heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
<strong>Output:</strong> 4
<strong>Explanation:</strong> Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 &gt;= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 &lt; 7.
- Go to building 3 without using ladders nor bricks since 7 &gt;= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 &lt; 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= heights.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= heights[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>0 &lt;= bricks &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= ladders &lt;= heights.length</code></li>
</ul>

'''
Greedy, you want to conserve as much ladders as you can

Pseudocode
- calculate differences and put them in pq (diff, index)
- As you go index by index, if you pass by index, use the ladder, otherwise use your bricks
- If you don't have enough bricks, use your ladder, if you don't have ladder, break out
- The idea here is that let's say you don't even reach the index you're supposed to use the ladder on, it wouldn't have mattered anyways because you're going to use ladders for the last few steps which are "greater" -> actually I don't believe in this

- Ah, similar but use bricks as much as you can, if you don't have bricks anymore, see if you can take out the biggest 'brick" you used and replace with ladder

After looking at solution
- Much easier to say the other way around - always use ladders, and when you run out, take the smallest diff and use bricks
'''

class Solution:
    def furthestBuilding2(self, heights: List[int], bricks: int, ladders: int) -> int:
        pq = []
        for i in range(1, len(heights)):
            diff = heights[i] - heights[i - 1]
            if diff > 0:
                heappush(pq, diff)
                
                if len(pq) > ladders:
                    bricks -= heappop(pq)
                if bricks < 0:
                    return i - 1
        return len(heights) - 1
                    
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        pq = []
        for i in range(1, len(heights)):
            diff = heights[i] - heights[i - 1]
            if diff > 0:
                if bricks >= diff:
                    bricks -= diff
                    heappush(pq, -diff)
                elif ladders > 0:
                    ladders -= 1
                    if pq and -pq[0] > diff and -pq[0] + bricks >= diff:
                        bricks -= heappop(pq)
                        bricks -= diff
                        heappush(pq, -diff)
                        
                else:
                    return i - 1
        return len(heights) - 1
29200