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.

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>> &restrictions) {
        int MAXLEN = 1e9, res = 0;
        restrictions.push_back({1, 0});
        restrictions.push_back({n, MAXLEN});
        sort(restrictions.begin(), restrictions.end());
        int sz = restrictions.size();

        for (int i = 1; i < sz; i++) {
            restrictions[i][1] = min(restrictions[i][1],
                                     restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0]);
            restrictions[sz - i - 1][1] = min(restrictions[sz - i - 1][1],
                                              restrictions[sz - i][1] + restrictions[sz - i][0] - restrictions[sz - i - 1][0]);
        }

        for (int i = 0; i < sz - 1; i++) {
            int diff = abs(restrictions[i][1] - restrictions[i + 1][1]);
            int dis = restrictions[i + 1][0] - restrictions[i][0];
            res = max(res, dis < diff ? max(restrictions[i][1], restrictions[i + 1][1]) :
                           max(restrictions[i][1], restrictions[i + 1][1]) + (dis - diff) / 2);
        }
        return res;
    }
};