| 1 | class Solution: |
| 2 | def getSkyline(self, A: List[List[int]]) -> List[List[int]]: |
| 3 | n = len(A) |
| 4 | # If the given array of building contains only 1 or less building, we can |
| 5 | # directly return a corresponding skyline. |
| 6 | if n == 0: return [] |
| 7 | if n == 1: return [[A[0][0], A[0][2]], [A[0][1], 0]] |
| 8 | |
| 9 | # Otherwise, we shall recursively divide the buildings and merge the skylines. |
| 10 | # Cut the given skyline into two halves, get skyline from each half and merge |
| 11 | # them into a single skyline. |
| 12 | left_skyline = self.getSkyline(A[: n // 2]) |
| 13 | right_skyline = self.getSkyline(A[n // 2 :]) |
| 14 | return self.merge_sky(left_skyline, right_skyline) |
| 15 | |
| 16 | def merge_sky(self, left_skyline, right_skyline): |
| 17 | # Initalize left_pos=0, right_pos=0 as the pointer of left_skyline and right_skyline. |