1840. Maximum Building Height

Problem Statement

Hard

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] = [id_i, maxHeight_i] indicates that building id_i must have a height less than or equal to maxHeight_i.

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 <= 10⁹
0 <= restrictions.length <= min(n - 1, 10⁵)
2 <= id_i <= n
id_i is unique.
0 <= maxHeight_i <= 10⁹

Java

Source file

class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        int r = restrictions.length, maxm = 0, dist;
        if (r == 0)
            return n - 1;
        Arrays.sort(restrictions, (a, b) -> a[0] - b[0]);
        int[] sentinelLt = { 1, 0 }; // initialize sentinel node (leftmost)
        int[] sentinelRt = restrictions[r - 1][0] == n // if upper bound for last building is given
                ? restrictions[r - 1] // then, use it
                : new int[] { n, n - 1 }; // else, initialize sentinel node (rightmost)
        int[] prev = sentinelLt;
        for (int i = 0; i < r; i++) {
            dist = restrictions[i][0] - prev[0];
            restrictions[i][1] = Math.min(restrictions[i][1], prev[1] + dist);
            prev = restrictions[i];
        }
        dist = sentinelRt[0] - restrictions[r - 1][0];
        sentinelRt[1] = Math.min(sentinelRt[1], prev[1] + dist);
        prev = sentinelRt;
        for (int i = r - 1; i >= 0; i--) {  // Left->Right pass
            dist = prev[0] - restrictions[i][0];
            restrictions[i][1] = Math.min(restrictions[i][1], prev[1] + dist);
            prev = restrictions[i];
        }
        prev = sentinelLt;
        for (int i = 0; i < r; i++) {   // Right->Left pass
            dist = restrictions[i][0] - prev[0];
            maxm = Math.max(maxm, (prev[1] + restrictions[i][1] + dist) / 2);
            prev = restrictions[i];
        }
        if (restrictions[r - 1][0] != n) {  // Calc. max possible intermediary building (inflection)
            dist = n - restrictions[r - 1][0];
            maxm = Math.max(maxm, (sentinelRt[1] + restrictions[r - 1][1] + dist) / 2);
        }
        // for (int[] res : restrictions)
        //     System.out.print(Arrays.toString(res) + "->");
        return maxm;
    }
}