# 1840. Maximum Building Height

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mi6vS6poXuN8B1G2w7s%2F-Mi6vZYz-_mvy-8hlNKm%2Fimage.png?alt=media\&token=b87fc6d3-c64c-4fa2-9f91-333738e688b3)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mi6vS6poXuN8B1G2w7s%2F-Mi6vbFUOkjsgoLDpOKj%2Fimage.png?alt=media\&token=7ae48f43-ff29-4ac3-89d6-abc9879c9404)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mi6vS6poXuN8B1G2w7s%2F-Mi6ve44zdX1B5GDP0kz%2Fimage.png?alt=media\&token=cf65996e-fef8-4333-a007-71cebf53e7a1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mi6vS6poXuN8B1G2w7s%2F-Mi6vhnNEeKml0ANatoC%2Fimage.png?alt=media\&token=88c4eca6-b7a9-41f1-99d7-cc2f2a3209c5)

<https://leetcode.com/problems/maximum-building-height/discuss/1429202/Java-Greedy-Clean-Solution-with-explanation-O(mlogm)>

time: O(mlogm)

space: O(m)

```java
class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        int[][] r = new int[restrictions.length+2][];
        for (int i = 0; i < restrictions.length; i++) {
            r[i] = restrictions[i];
        }
        r[r.length-2] = new int[]{1, 0}; // add first building
        r[r.length-1] = new int[]{n, 1_000_000_000}; // add n building
        
        Arrays.sort(r, (a, b) -> a[0] - b[0]);
        
        int m = r.length;
            
        for (int i = m-2; i >= 1; i--) { // from right <-
            r[i][1] = Math.min(r[i][1], r[i+1][1] + r[i+1][0] - r[i][0]);
        }
        
        int res = 0;
        for (int i = 1; i < m; i++) { // from left -> // i = 0, 都是 0 所以不管
            r[i][1] = Math.min(r[i][1], r[i-1][1] + r[i][0] - r[i-1][0]);
            
            // last step: caculate the peak of two limit building (each buildings)
            int distance = r[i][0] - r[i-1][0];
        		int buildDiff = Math.abs(r[i][1] - r[i-1][1])
        		int peak = (distance - buildDiff)/2;
        		int maxBuildingHeight	=	Math.max(r[i][1], r[i-1][1]);
            res = Math.max(res, maxBuilding + peak);
        }
        
        return res;
    }
}

  
/*
   h
   
4.    4. 
x     y 

h = 4 + (y - x)/2 
-------------------------------------   
   h

3     4
3 add 1 to 4, fix to same high, this 1 substract from dist

h = 4 + (y - x - 1)/2 

*/
```