1840. Maximum Building Height Hard

1/**
2 * [1840] Maximum Building Height
3 *
4 * 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.
5 * However, there are city restrictions on the heights of the new buildings:
6 * 
7 * 	The height of each building must be a non-negative integer.
8 * 	The height of the first building must be 0.
9 * 	The height difference between any two adjacent buildings cannot exceed 1.
10 * 
11 * 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.
12 * It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.
13 * Return the maximum possible height of the tallest building.
14 *  
15 * Example 1:
16 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex1-1.png" style="width: 400px; height: 253px;" />
17 * Input: n = 5, restrictions = [[2,1],[4,1]]
18 * Output: 2
19 * Explanation: The green area in the image indicates the maximum allowed height for each building.
20 * We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.
21 * Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex2.png" style="width: 500px; height: 269px;" />
23 * Input: n = 6, restrictions = []
24 * Output: 5
25 * Explanation: The green area in the image indicates the maximum allowed height for each building.
26 * We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.
27 * 
28 * Example 3:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex3.png" style="width: 500px; height: 187px;" />
30 * Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
31 * Output: 5
32 * Explanation: The green area in the image indicates the maximum allowed height for each building.
33 * 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.
34 * 
35 *  
36 * Constraints:
37 * 
38 * 	2 <= n <= 10^9
39 * 	0 <= restrictions.length <= min(n - 1, 10^5)
40 * 	2 <= idi <= n
41 * 	idi is unique.
42 * 	0 <= maxHeighti <= 10^9
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/maximum-building-height/
48// discuss: https://leetcode.com/problems/maximum-building-height/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn max_building(n: i32, restrictions: Vec<Vec<i32>>) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_1840() {
66    }
67}
68