maximum-building-height.java

class Solution {
    public int maxBuilding(int n, int[][] restrictions) {

        int m = restrictions.length;

        int[][] arr = new int[m + 2][2];

        arr[0][0] = 1;
        arr[0][1] = 0;

        for (int i = 0; i < m; i++) {
            arr[i + 1] = restrictions[i];
        }

        arr[m + 1][0] = n;
        arr[m + 1][1] = n - 1;

        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        int len = arr.length;

        // Left -> Right
        for (int i = 1; i < len; i++) {
            int d = arr[i][0] - arr[i - 1][0];
            arr[i][1] = Math.min(arr[i][1],
                                 arr[i - 1][1] + d);
        }

        // Right -> Left
        for (int i = len - 2; i >= 0; i--) {
            int d = arr[i + 1][0] - arr[i][0];
            arr[i][1] = Math.min(arr[i][1],
                                 arr[i + 1][1] + d);
        }

        long ans = 0;

        for (int i = 1; i < len; i++) {

            long x1 = arr[i - 1][0];
            long h1 = arr[i - 1][1];

            long x2 = arr[i][0];
            long h2 = arr[i][1];

            long d = x2 - x1;

            long peak = (h1 + h2 + d) / 2;

            ans = Math.max(ans, peak);
        }

        return (int) ans;
    }
}