<p>You want to build <code>n</code> new buildings in a city. The new buildings will be built in a line and are labeled from <code>1</code> to <code>n</code>.</p>

<p>However, there are city restrictions on the heights of the new buildings:</p>

<ul>
	<li>The height of each building must be a non-negative integer.</li>
	<li>The height of the first building <strong>must</strong> be <code>0</code>.</li>
	<li>The height difference between any two adjacent buildings <strong>cannot exceed</strong> <code>1</code>.</li>
</ul>

<p>Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array <code>restrictions</code> where <code>restrictions[i] = [id<sub>i</sub>, maxHeight<sub>i</sub>]</code> indicates that building <code>id<sub>i</sub></code> must have a height <strong>less than or equal to</strong> <code>maxHeight<sub>i</sub></code>.</p>

<p>It is guaranteed that each building will appear <strong>at most once</strong> in <code>restrictions</code>, and building <code>1</code> will <strong>not</strong> be in <code>restrictions</code>.</p>

<p>Return <em>the <strong>maximum possible height</strong> of the <strong>tallest</strong> building</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex1-1.png" style="width: 400px; height: 253px;" />
<pre>
<strong>Input:</strong> n = 5, restrictions = [[2,1],[4,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex2.png" style="width: 500px; height: 269px;" />
<pre>
<strong>Input:</strong> n = 6, restrictions = []
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/08/ic236-q4-ex3.png" style="width: 500px; height: 187px;" />
<pre>
<strong>Input:</strong> n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
<strong>Output:</strong> 5
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= restrictions.length &lt;= min(n - 1, 10<sup>5</sup>)</code></li>
	<li><code>2 &lt;= id<sub>i</sub> &lt;= n</code></li>
	<li><code>id<sub>i</sub></code>&nbsp;is <strong>unique</strong>.</li>
	<li><code>0 &lt;= maxHeight<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        # line 1 to n
        # h >= 0
        # first h == 0
        # max diff of buildings 1
        # restrictions[i] is the height limit for i

        # return max possible height
        
        # max height of a building depends on the max height of building(s) to the left and right, plus one
        # limits obviously restrict height too

        # restrictions is [id, max_h] pairs, up to 1e5 of them
        # there are n=1e9 buildings labeled 1..n

        # how can we build up the skyline?
        
        # 2..n ideally have height 2
        # 3..n height 3
        # etc.
        #
        # but a restriction means a house is "locked in"
        #    then if k1 .. k2 has height limits on k1 and k2
        #       then k1+1 .. k2-1 have a max height
        #       etc. until we find another max height that limits progress

        # another idea: stack question
        # we can iterate among the building restrictions in order by id
        # from the left we know the limit, but we don't yet know the right limit, hence the stack
        # stack is something like [l, lh, r, rh]
        #      deltas in that interval are r-l
        #      range(lh, rh) of those need to bring smaller up to larger
        #      what goes up must come down
        #      so max height is r-l-(max(lh, rh)-min(lh, rh))//2
        
        restrictions.sort()

        # each limit we see is
        #     a left limit: prevents later buildings from getting really tall
        #     and also a right limit, prevents earlier buildings from getting really tall
        
        # for a building at index i:
        #         limited by building at l with max height lh according to lh+(i-l) == lh-l+i
        #                                r                 rh              rh+(r-i) == rh+r-i
        # so we want the lowest lh-l on the left and rh+r on the right
        #     max on left: cumulative as we process left to right
        #     max on right: O(N) time and space to preprocess a list of limits
        #                       decreasing stack formed by processing right to left
        #
        # rlims = [(n, n-1+n)] # idx, max height limit, descending by idx
        # for r, rh in reversed(restrictions):
        #     lim = r+rh
        #     if lim < rlims[-1][0] + rlims[-1][1]: rlims.append((r, rh))

        # # makes sure we include the final range ...n with height "limit" n-1 in our answer
        # # (n-1 is the max possible height with no restrictions, more of a guard element
        # #  than an actual limit)
        # def allRestrictions() -> Iterator[tuple[int, int]]:
        #     for rest in restrictions: yield rest
        #     yield [n, n-1]

        # l = 1
        # lh = 0
        # ans = 0
        # for i, h in allRestrictions():
        #     # left limit on height comes from l, lh
        #     # right limit on height comes from top of rlims stack, the cumulative most restrictive limit on the right

        #     r, rh = rlims[-1]

        #     lo = min(lh, rh)
        #     hi = max(lh, rh)
        #     if lo+r-l <= hi:
        #         # print(f"Max height on {l=} .. {i=} is {lo+r-l}")
        #         # max height limited by lower one
        #         ans = max(ans, lo+r-l)
        #     else:
        #         # spend hi-lo of the r-l increments to bring lo up to hi
        #         # then spend another pair of remaining increments to gain height in a pyramid-like pattern
        #         # print(f"Max height on {l=} .. {i=} is {hi + (r-l-(hi-lo))//2}")
        #         ans = max(ans, hi + (r-l-(hi-lo))//2)

        #     if h-i < lh-l:
        #         l, lh = i, h # new limit on the left

        #     if rlims[-1][0] == i: 
        #         # we're at a right limit, later indices don't have this on the right
        #         # so we pop it (if it's restrictive on the left then we'll have included
        #         # it in the prior if statement)
        #         rlims.pop()

        # return ans


        # better: from looking at other solutions we can modify the restrictions in place
        #     first pass left to right: if current element is limited by a prior one, limit the current one
        #     next pass right to left: same idea, if limited by later element then limit the current one
        
        if not restrictions: return n-1

        restrictions.append([1, 0])
        restrictions.append([n, n-1])
        restrictions.sort()

        N = len(restrictions)
        
        # forward pass: if there's a left limit that reduces the max height of i, change
        # i's restriction to the lower limit imposed from the left
        for i in range(1, N):
            prev_idx, prev_h = restrictions[i-1]
            curr_idx = restrictions[i][0]
            
            # with curr_idx-prev_idx increments the max height is prev_h + differenceInIndices
            restrictions[i][1] = min(restrictions[i][1], prev_h + curr_idx - prev_idx)

        # reverse pass: same idea, but account for right limits
        for i in range(N-2, -1, -1):
            next_idx, next_h = restrictions[i+1]
            curr_idx = restrictions[i][0]

            restrictions[i][1] = min(restrictions[i][1], next_h + next_idx - curr_idx)

        # third pass: for each interval find the max height, record cumulative max height
        ans = 0
        for i in range(N-1):
            l, lh = restrictions[i]
            r, rh = restrictions[i+1]

            # spend range increments to make lh == rh, then pairs to make a pyramid pattern to get max height
            lo = min(lh, rh)
            hi = lh+rh-lo
            ans = max(ans, hi + (r-l-(hi-lo))//2)

        return ans
54400