Maximum Building Height

// Accepted solution for LeetCode #1840: Maximum Building Height
class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        List<int[]> r = new ArrayList<>();
        r.addAll(Arrays.asList(restrictions));
        r.add(new int[] {1, 0});
        Collections.sort(r, (a, b) -> a[0] - b[0]);
        if (r.get(r.size() - 1)[0] != n) {
            r.add(new int[] {n, n - 1});
        }
        int m = r.size();
        for (int i = 1; i < m; ++i) {
            int[] a = r.get(i - 1), b = r.get(i);
            b[1] = Math.min(b[1], a[1] + b[0] - a[0]);
        }
        for (int i = m - 2; i > 0; --i) {
            int[] a = r.get(i), b = r.get(i + 1);
            a[1] = Math.min(a[1], b[1] + b[0] - a[0]);
        }
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            int[] a = r.get(i), b = r.get(i + 1);
            int t = (a[1] + b[1] + b[0] - a[0]) / 2;
            ans = Math.max(ans, t);
        }
        return ans;
    }
}

// Accepted solution for LeetCode #1840: Maximum Building Height
func maxBuilding(n int, restrictions [][]int) (ans int) {
	r := restrictions
	r = append(r, []int{1, 0})
	sort.Slice(r, func(i, j int) bool { return r[i][0] < r[j][0] })
	if r[len(r)-1][0] != n {
		r = append(r, []int{n, n - 1})
	}
	m := len(r)
	for i := 1; i < m; i++ {
		r[i][1] = min(r[i][1], r[i-1][1]+r[i][0]-r[i-1][0])
	}
	for i := m - 2; i > 0; i-- {
		r[i][1] = min(r[i][1], r[i+1][1]+r[i+1][0]-r[i][0])
	}
	for i := 0; i < m-1; i++ {
		t := (r[i][1] + r[i+1][1] + r[i+1][0] - r[i][0]) / 2
		ans = max(ans, t)
	}
	return ans
}

# Accepted solution for LeetCode #1840: Maximum Building Height
class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        r = restrictions
        r.append([1, 0])
        r.sort()
        if r[-1][0] != n:
            r.append([n, n - 1])
        m = len(r)
        for i in range(1, m):
            r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0])
        for i in range(m - 2, 0, -1):
            r[i][1] = min(r[i][1], r[i + 1][1] + r[i + 1][0] - r[i][0])
        ans = 0
        for i in range(m - 1):
            t = (r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) // 2
            ans = max(ans, t)
        return ans

// Accepted solution for LeetCode #1840: Maximum Building Height
/**
 * [1840] Maximum Building Height
 *
 * 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:
 *
 * 	The height of each building must be a non-negative integer.
 * 	The height of the first building must be 0.
 * 	The height difference between any two adjacent buildings cannot exceed 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex1-1.png" style="width: 400px; height: 253px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex2.png" style="width: 500px; height: 269px;" />
 * 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex3.png" style="width: 500px; height: 187px;" />
 * 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 <= 10^9
 * 	0 <= restrictions.length <= min(n - 1, 10^5)
 * 	2 <= idi <= n
 * 	idi is unique.
 * 	0 <= maxHeighti <= 10^9
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/maximum-building-height/
// discuss: https://leetcode.com/problems/maximum-building-height/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn max_building(n: i32, restrictions: Vec<Vec<i32>>) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1840_example_1() {
        let n = 5;
        let restrictions = vec![vec![2, 1], vec![4, 1]];

        let result = 2;

        assert_eq!(Solution::max_building(n, restrictions), result);
    }

    #[test]
    #[ignore]
    fn test_1840_example_2() {
        let n = 6;
        let restrictions = vec![];

        let result = 5;

        assert_eq!(Solution::max_building(n, restrictions), result);
    }

    #[test]
    #[ignore]
    fn test_1840_example_3() {
        let n = 3;
        let restrictions = vec![vec![5, 3], vec![2, 5], vec![7, 4], vec![10, 3]];

        let result = 5;

        assert_eq!(Solution::max_building(n, restrictions), result);
    }
}

// Accepted solution for LeetCode #1840: Maximum Building Height
function maxBuilding(n: number, restrictions: number[][]): number {
    restrictions.push([1, 0]);
    restrictions.sort((a, b) => a[0] - b[0]);
    if (restrictions[restrictions.length - 1][0] !== n) {
        restrictions.push([n, n - 1]);
    }

    const m = restrictions.length;
    for (let i = 1; i < m; ++i) {
        restrictions[i][1] = Math.min(
            restrictions[i][1],
            restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0],
        );
    }

    for (let i = m - 2; i >= 0; --i) {
        restrictions[i][1] = Math.min(
            restrictions[i][1],
            restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0],
        );
    }

    let ans = 0;
    for (let i = 0; i < m - 1; ++i) {
        const t = Math.floor(
            (restrictions[i][1] +
                restrictions[i + 1][1] +
                restrictions[i + 1][0] -
                restrictions[i][0]) /
                2,
        );
        ans = Math.max(ans, t);
    }

    return ans;
}