We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Building Height

Difficulty: Hard

Problem 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, given as a 2D integer array restrictions where restrictions[i] = [id_i, maxHeight_i] indicates that building id_i must have a height less than or equal to maxHeight_i. Return the maximum possible height of the tallest building.

Key Insights

  • The first building must have a height of 0.
  • The height of adjacent buildings can only differ by at most 1.
  • Restrictions can limit the maximum height of certain buildings, affecting the overall height distribution.
  • The problem can be approached by considering the heights from both ends (left and right) towards the restricted buildings and calculating the maximum heights accordingly.

Space and Time Complexity

Time Complexity: O(m log m) where m is the number of restrictions, due to sorting. Space Complexity: O(m) for storing the restrictions.

Solution

To solve the problem, we can follow these steps:

  1. Sort the restrictions based on the building id.
  2. Add the boundaries for building 1 with a height of 0 and building n with a height of infinity.
  3. Iterate through the sorted restrictions and calculate the maximum height possible for each segment between two restrictions.
  4. Use the formula for the maximum height achievable in each segment, taking into account the heights allowed by the restrictions and the adjacent building height difference constraint.
  5. Return the maximum height found.

Code Solutions

def maxBuilding(n, restrictions):
    restrictions.append([1, 0])  # Building 1 must be 0
    restrictions.append([n, n])  # Building n can be infinitely high
    restrictions.sort()  # Sort restrictions based on building id
    
    # Step to calculate max heights from left to right
    for i in range(1, len(restrictions)):
        id1, h1 = restrictions[i - 1]
        id2, h2 = restrictions[i]
        # Calculate the maximum height that can be achieved between two restrictions
        max_height = (h1 + (id2 - id1)) // 2
        restrictions[i][1] = min(h2, max_height)
    
    # Step to calculate max heights from right to left
    for i in range(len(restrictions) - 2, -1, -1):
        id1, h1 = restrictions[i + 1]
        id2, h2 = restrictions[i]
        # Adjust the height considering the maximum allowed from the right
        max_height = (h2 + (id1 - id2)) // 2
        restrictions[i][1] = min(h1, max_height)
    
    # Step to find the maximum possible height of the tallest building
    max_height = 0
    for i in range(1, len(restrictions)):
        id1, h1 = restrictions[i - 1]
        id2, h2 = restrictions[i]
        # Calculate the height at the middle of the two buildings
        height_between = (h1 + h2 + (id2 - id1)) // 2
        max_height = max(max_height, height_between)
    
    return max_height
← Back to All Questions