Maximize the Skyline Under Sparse Height Caps

### Problem There are `n` buildings labeled `1..n`. Heights are nonnegative integers, building 1 has height zero, and adjacent heights differ by at most one. Each `[id,maxHeight]` in `restrictions` imposes an upper bound. Return the greatest height that any building can attain while satisfying all rules. ```cpp class Solution { public: int maxBuilding(int n, vector<vector<int>>& restrictions); }; ``` ### Examples **Example 1:** ```text n = 4, restrictions = [[3,0]] Output: 1 Explanation: Heights [0,1,0,1] satisfy the cap and attain the maximum. ``` **Example 2:** ```text n = 7, restrictions = [[4,1]] Output: 4 Explanation: Heights [0,1,2,1,2,3,4] work; the capped building limits the final height to 4. ``` ### Constraints - `2 <= n <= 10^9`. - `0 <= restrictions.length <= min(n-1,10^5)`. - Restriction IDs are unique and in `[2,n]`; building 1 is absent. - Each maximum height lies in `[0,10^9]`. ### Clarifying Questions Caps are upper bounds, not required exact heights. Heights may be zero, unlike variants requiring positive heights. ```hint Inspect the structure Are the supplied height caps equalities or upper bounds, and which building has a fixed height? ``` ### Reasoning checkpoints - Show that the claimed maximum belongs to a skyline satisfying the fixed first height, every cap, and every neighbor bound. - Prove that a larger height is impossible and handle the stated sparse-restriction and building-count limits. ### Optional extensions How would you recover an index attaining the maximum from each interval’s tent intersection?