The Skyline Problem
1. Divide and Conquer
The divide and conqure solution can be thought from base case when we have two buildings, one in left and one in right.This is the smallest number of skylines. The possible 4 arrangements are
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1.
____________ ________
| | | |
| | | |
| | | |
| | | |
2.
_____________
| |
| |
______|____ |
| | | |
| | | |
| | | |
| | | |
3.
_________
| |
| |
______|_________|________
| | | |
| | | |
| | | |
| | | |
4.
_________
| |
| |
|_________|________
| | |
| | |
| | |
| | |
5.
____________________
| | | |
| | | |
| | | |
| | | |
Now we need to design our merge step keeping in mind these 4 cases.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
if len(buildings)==0:
return []
if len(buildings)==1:
x1,x2,y = buildings[0]
return [[x1,y],[x2,0]]
n=len(buildings)
left = self.getSkyline(buildings[:n//2])
right = self.getSkyline(buildings[n//2:])
return self.merge(left,right)
def merge(self,left,right):
output = []
currY,leftY,rightY=0,0,0 # this is for us to keep history
left_l,left_r,right_l,right_r = 0,len(left),0,len(right)
while left_l < left_r and right_l < right_r:
if left[left_l][0] < right[right_l][0]:
x,y = left[left_l]
leftY= y
left_l+=1
else:
x,y = right[right_l]
rightY= y
right_l+=1
maxY = max(leftY,rightY) # to handle overlapping case
if maxY!=currY:
# need change
if len(output)==0: # for very first
output.append([x,maxY])
elif output[-1][0]==x: # for case 4
output[-1][1]=maxY
else:
output.append([x,maxY]) # for case 1,2,3
currY=maxY
while left_l < left_r: # for left over
x,maxY = left[left_l]
if maxY!=currY:
# need change
if len(output)==0:
output.append([x,maxY])
elif output[-1][0]==x:
output[-1][1]=maxY
else:
output.append([x,maxY])
left_l+=1
currY=maxY
while right_l < right_r:
x,maxY = right[right_l]
if maxY!=currY:
# need change
if len(output)==0:
output.append([x,maxY])
elif output[-1][0]==x:
output[-1][1]=maxY
else:
output.append([x,maxY])
right_l+=1
currY=maxY
return output;