Reach the Furthest Building with Limited Climbing Supplies

### Problem Starting at index 0 in `heights`, move to each next building in order. A flat or downward step is free. An upward step of height d consumes either d bricks or one ladder. Given `bricks` and `ladders`, return the greatest index you can reach. ```cpp class Solution { public: int furthestBuilding(vector<int>& heights, int bricks, int ladders); }; ``` ### Examples **Example 1:** ```text heights = [1,5,6,10], bricks = 5, ladders = 1 Output: 3 Explanation: Use a ladder on one rise of 4 and bricks on the other rise of 4 and the rise of 1. ``` **Example 2:** ```text heights = [7,3,8], bricks = 4, ladders = 0 Output: 1 Explanation: Descending to index 1 is free, but the next rise needs 5 bricks. ``` ### Constraints - `1 <= heights.length <= 10^5`. - Each height is in `[1,10^6]`. - `0 <= bricks <= 10^9`. - `0 <= ladders <= heights.length`. ### Clarifying Questions Return a zero-based building index, not a count of buildings. A ladder is consumed by one rise regardless of its height. ```hint Inspect the structure How would you verify that a claimed destination respects both the brick budget and the number of ladders? ``` ### Reasoning checkpoints - Show that the claimed destination is reachable within both resource budgets. - Prove that no farther destination is reachable, with free descents and unequal rise sizes handled correctly. ### Optional extensions How would binary searching the destination compare with maintaining the optimal prefix allocation online?