Watch 10 video solutions for Maximum Building Height, a hard level problem involving Array, Math, Sorting. This walkthrough by Ashish Pratap Singh has 1,002,200 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.
However, there are city restrictions on the heights of the new buildings:
0.1.Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [idi, maxHeighti] indicates that building idi must have a height less than or equal to maxHeighti.
It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.
Return the maximum possible height of the tallest building.
Example 1:
Input: n = 5, restrictions = [[2,1],[4,1]] Output: 2 Explanation: The green area in the image indicates the maximum allowed height for each building. We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.
Example 2:
Input: n = 6, restrictions = [] Output: 5 Explanation: The green area in the image indicates the maximum allowed height for each building. We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.
Example 3:
Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]] Output: 5 Explanation: The green area in the image indicates the maximum allowed height for each building. We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.
Constraints:
2 <= n <= 1090 <= restrictions.length <= min(n - 1, 105)2 <= idi <= nidi is unique.0 <= maxHeighti <= 109