1840. Maximum Building Height

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

time: O(mlogm)

space: O(m)

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 

*/