Furthest Building you can reach

XXX. Furthest Building You Can Reach

Greedy

Priority Queue

Problem Statement:

You are given an array buildings where buildings[i] represents the height of the i-th building. You can use ladders or bricks to jump to the next building if its height is greater than the current one. The goal is to determine the furthest building you can reach using the given number of bricks and ladders.

Approach:

1. Use a PriorityQueue (min-heap) to keep track of the heights of the climbs that require ladders.
2. For each building transition:
   • If the height difference is positive, add it to the heap.
   • If the heap size exceeds the number of ladders, remove the smallest height difference and use bricks instead.
   • If bricks run out, return the current building index as the furthest reachable building.
3. If the loop completes, all buildings are reachable, and the result is the last building index.

Complexity:

Time Complexity: O(n log k), where n is the number of buildings and k is the number of ladders (size of the heap).
Space Complexity: O(k) for the heap.

Java Implementation:

public int furthestBuilding(int[] buildings, int bricks, int ladders) {
    // Min-heap to store the heights of the climbs
    PriorityQueue pq = new PriorityQueue<>();

    // Traverse the buildings
    for (int i = 0; i < buildings.length - 1; i++) {
        int d = buildings[i + 1] - buildings[i];

        // If there is a height difference, add it to the heap
        if (d > 0)
            pq.add(d);

        // If the heap exceeds the number of ladders, use bricks for the smallest climb
        if (pq.size() > ladders)
            bricks -= pq.poll();

        // If bricks are exhausted, return the current building index
        if (bricks < 0)
            return i;
    }

    // If we reach the end, return the last building index
    return buildings.length - 1;
}