aboutsummaryrefslogtreecommitdiff
path: root/max_increase_city_skyline.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_increase_city_skyline.py')
-rw-r--r--max_increase_city_skyline.py42
1 files changed, 42 insertions, 0 deletions
diff --git a/max_increase_city_skyline.py b/max_increase_city_skyline.py
new file mode 100644
index 0000000..e3c7091
--- /dev/null
+++ b/max_increase_city_skyline.py
@@ -0,0 +1,42 @@
+# 807. Max Increase to Keep City Skyline
+
+"""
+there is a city composed of 'n * n' blocks where each block contains a single
+building shaped like a vertical square prisum. you are given 0 idxed 'n * n'
+integer matrix 'grid' where 'grid[r][c]' represents the height of the
+building located in the block at row 'r' and column 'c'. a city's skiline is
+the outer contour formed by all the building =hen viewing the side of the
+city from a distance. the skyline from a distance. the skyline from each
+cardinal direction, north, east, south, and west may be different. we are
+allowed to increase the height of any number of buildings by any amount. the
+height of a 0-height building can also be increased. however, increasing the
+height of a building should not affect the city's skyline from any cardinal
+direction. return the maximum total sum that the height of the buildings can
+be increased by without changing the city's skyline from any cardinal
+direction
+"""
+
+
+class Solution(object):
+ def maxIncreaseKeepingSkyline(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ sum = 0
+ l1 = [max(i) for i in zip(*grid)]
+ l2 = [max(i) for i in grid]
+ for i in range(len(grid)):
+ for j in range(len(grid)):
+ sum += min(l1[j], l2[i]) - grid[i][j]
+ return sum
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxIncreaseKeepingSkyline(
+ grid=[[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]]
+ )
+ )
+ print(obj.maxIncreaseKeepingSkyline(grid=[[0, 0, 0], [0, 0, 0], [0, 0, 0]]))