Use bricks and ladders to jump between buildings. Ladders used for tallest jumps. Find farthest building reachable.
Input: heights=[4,2,7,6,9,14,12], bricks=5, ladders=1 → Output: 4
Input: heights=[4,12,2,7,3,18,20,3,19], bricks=10, ladders=2 → Output: 7
Use a min-heap of size ladders. For each upward jump, add to heap. When heap exceeds ladders size, use bricks for smallest jump in heap.
- For each gap heights[i+1]-heights[i] > 0
- Add gap to min-heap
- If heap size > ladders, use bricks for heap.poll() (smallest jump)
- If not enough bricks, return i
- Return last index
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < heights.length - 1; i++) {
int diff = heights[i+1] - heights[i];
if (diff <= 0) continue;
pq.offer(diff);
if (pq.size() > ladders) {
bricks -= pq.poll();
}
if (bricks < 0) return i;
}
return heights.length - 1;
}
- Time Complexity: O(n log L)
- Space Complexity: O(L)