Formatted question description: https://leetcode.ca/all/1840.html

# 1840. Maximum Building Height

## Level

Hard

## Description

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^9`

`0 <= restrictions.length <= min(n - 1, 10^5)`

`2 <= id_i <= n`

`id_i`

is unique.`0 <= maxHeight_i <= 10^9`

## Solution

Sort `restrictions`

according to the `id`

values. Then loop over `restrictions`

forward and backward to determine the actual maximum possible height of each element in `restrictions`

. Next, for two adjacent restrictions `[i, a]`

and `[j, b]`

where `i < j`

, the maximum possible height in the ranges `[i, j]`

is `(j - i + Math.abs(b - a)) / 2 + Math.min(a, b)`

. The last thing is to calculate the maximum possible height of the building with `id = n`

. Finally, return the maximum possible height among all `n`

buildings.

```
class Solution {
public int maxBuilding(int n, int[][] restrictions) {
Arrays.sort(restrictions, new Comparator<int[]>() {
public int compare(int[] restriction1, int[] restriction2) {
return restriction1[0] - restriction2[0];
}
});
int maxHeight = 0;
int length = restrictions.length;
int prevId = 1, prevHeight = 0;
for (int i = 0; i < length; i++) {
int[] restriction = restrictions[i];
int currId = restriction[0], currHeight = restriction[1];
int difference = currId - prevId;
restrictions[i][1] = Math.min(restrictions[i][1], prevHeight + difference);
prevId = currId;
prevHeight = restrictions[i][1];
}
for (int i = length - 2; i >= 0; i--) {
int difference = restrictions[i + 1][0] - restrictions[i][0];
restrictions[i][1] = Math.min(restrictions[i][1], restrictions[i + 1][1] + difference);
}
prevId = 1;
prevHeight = 0;
for (int i = 0; i < length; i++) {
int[] restriction = restrictions[i];
int currId = restriction[0], currHeight = restriction[1];
int difference = currId - prevId;
restrictions[i][1] = Math.min(restrictions[i][1], prevHeight + difference);
int heightDifference = Math.abs(currHeight - prevHeight);
int curMaxHeight = (difference + heightDifference) / 2 + Math.min(prevHeight, currHeight);
maxHeight = Math.max(maxHeight, curMaxHeight);
prevId = currId;
prevHeight = currHeight;
}
int lastHeight = prevHeight + (n - prevId);
maxHeight = Math.max(maxHeight, lastHeight);
return maxHeight;
}
}
```