The “Max Increase to Keep City Skyline” problem involves determining how much we can increase the height of buildings in a city grid while maintaining the skyline view. Each building’s height can be increased, but it must not exceed the constraints set by the maximum heights allowed for each row and each column.
Problem Statement
Given an n x m
2D grid representing the heights of buildings, you are allowed to increase the height of buildings, but the new height of a building at position (i, j)
must not exceed the minimum of the maximum heights of its corresponding row and column. Your task is to calculate the maximum total increase in building heights.
C# Implementation
Here’s how to implement this in C#:
using System;
public class CitySkyline
{
public static int MaxIncreaseKeepingSkyline(int[][] grid)
{
int n = grid.Length; // Number of rows
int m = grid[0].Length; // Number of columns
// Arrays to hold the max heights for each row and each column
int[] maxRow = new int[n];
int[] maxCol = new int[m];
// Determine the maximum heights for rows and columns
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
maxRow[i] = Math.Max(maxRow[i], grid[i][j]);
maxCol[j] = Math.Max(maxCol[j], grid[i][j]);
}
}
int totalIncrease = 0;
// Calculate the maximum increase for each building
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// The max height we can set for this building
int allowedHeight = Math.Min(maxRow[i], maxCol[j]);
// Increase we can make
totalIncrease += allowedHeight - grid[i][j];
}
}
return totalIncrease; // Return the total increase possible
}
public static void Main(string[] args)
{
int[][] grid = new int[][]
{
new int[] { 3, 0, 8, 4 },
new int[] { 2, 4, 5, 0 },
new int[] { 5, 6, 3, 2 },
new int[] { 0, 0, 1, 1 }
};
int result = MaxIncreaseKeepingSkyline(grid);
Console.WriteLine($"The maximum increase to keep the city skyline is: {result}");
}
}
Explanation
-
Data Structure:
- The grid is represented as a 2D array (
int[][]
), where each element represents the height of a building.
- The grid is represented as a 2D array (
-
MaxIncreaseKeepingSkyline Method:
- This method computes the maximum increase in building heights while maintaining the skyline.
-
Finding Maximum Heights:
- We create two arrays:
maxRow
to store the maximum height of buildings in each row andmaxCol
to store the maximum height in each column. - We iterate through the grid and update these arrays accordingly.
- We create two arrays:
-
Calculating Possible Increases:
- We initialize a variable
totalIncrease
to keep track of the total increase in heights. - For each building in the grid, we calculate the allowed height, which is the minimum of the maximum height of its row and its column.
- The increase for that building is computed as
allowedHeight - currentHeight
and added tototalIncrease
.
- We initialize a variable
-
Return Value:
- After iterating through the grid, the method returns the total possible increase in heights.
-
Main Method:
- In the
Main
method, we define a sample grid and call theMaxIncreaseKeepingSkyline
method to get the result, which is then printed.
- In the
Complexity Analysis
- Time Complexity: (O(n \cdot m)) since we iterate over the grid to determine max heights and then again to calculate the increases.
- Space Complexity: (O(n + m)) for storing the maximum heights of rows and columns.
Usage
You can modify the grid
variable in the Main
method to test different configurations. This implementation efficiently calculates the maximum increase in building heights while respecting the skyline constraints, providing an optimal solution to the problem.