1840. Maximum Building Height

Description

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.

 

Example 1:

Input: n = 5, restrictions = [[2,1],[4,1]]
Output: 2
Explanation: 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.

Example 2:

Input: n = 6, restrictions = []
Output: 5
Explanation: 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.

Example 3:

Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
Output: 5
Explanation: 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.

 

Constraints:

• 2 <= n <= 109
• 0 <= restrictions.length <= min(n - 1, 105)
• 2 <= idi <= n
• idi is unique.
• 0 <= maxHeighti <= 109

 

Solutions

Solution: Math

• Time complexity: O(mlogm)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @param {number[][]} restrictions
 * @return {number}
 */
const maxBuilding = function (n, restrictions) {
  restrictions.push([1, 0], [n, n - 1]);
  restrictions.sort((a, b) => a[0] - b[0]);

  const m = restrictions.length;
  let result = 0;

  for (let index = 1; index < m; index++) {
    const [l, hl] = restrictions[index - 1];
    const [r, hr] = restrictions[index];
    const interval = r - l;

    restrictions[index][1] = Math.min(hr, interval + hl);
  }

  for (let index = m - 2; index >= 0; index--) {
    const [l, hl] = restrictions[index];
    const [r, hr] = restrictions[index + 1];
    const interval = r - l;

    restrictions[index][1] = Math.min(hl, interval + hr);
  }

  for (let index = 1; index < m; index++) {
    const [l, hl] = restrictions[index - 1];
    const [r, hr] = restrictions[index];
    const interval = r - l - 1;
    const highest = Math.max(hl, hr) + Math.ceil((interval - Math.abs(hr - hl)) / 2);

    result = Math.max(highest, result);
  }

  return result;
};