Welcome to Subscribe On Youtube
1642. Furthest Building You Can Reach
Description
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
(0indexed),
 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 (0indexed) you can reach if you use the given ladders and bricks optimally.
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 Output: 4 Explanation: Starting at building 0, you can follow these steps:  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 < 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 < 9. It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0 Output: 3
Constraints:
1 <= heights.length <= 10^{5}
1 <= heights[i] <= 10^{6}
0 <= bricks <= 10^{9}
0 <= ladders <= heights.length
Solutions

class Solution { public int furthestBuilding(int[] heights, int bricks, int ladders) { PriorityQueue<Integer> q = new PriorityQueue<>(); int n = heights.length; for (int i = 0; i < n  1; ++i) { int a = heights[i], b = heights[i + 1]; int d = b  a; if (d > 0) { q.offer(d); if (q.size() > ladders) { bricks = q.poll(); if (bricks < 0) { return i; } } } } return n  1; } }

class Solution { public: int furthestBuilding(vector<int>& heights, int bricks, int ladders) { priority_queue<int, vector<int>, greater<int>> q; int n = heights.size(); for (int i = 0; i < n  1; ++i) { int a = heights[i], b = heights[i + 1]; int d = b  a; if (d > 0) { q.push(d); if (q.size() > ladders) { bricks = q.top(); q.pop(); if (bricks < 0) { return i; } } } } return n  1; } };

class Solution: def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) > int: h = [] for i, a in enumerate(heights[:1]): b = heights[i + 1] d = b  a if d > 0: heappush(h, d) if len(h) > ladders: bricks = heappop(h) if bricks < 0: return i return len(heights)  1

func furthestBuilding(heights []int, bricks int, ladders int) int { q := hp{} n := len(heights) for i, a := range heights[:n1] { b := heights[i+1] d := b  a if d > 0 { heap.Push(&q, d) if q.Len() > ladders { bricks = heap.Pop(&q).(int) if bricks < 0 { return i } } } } return n  1 } type hp struct{ sort.IntSlice } func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() any { a := h.IntSlice v := a[len(a)1] h.IntSlice = a[:len(a)1] return v }