forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
the-skyline-problem.py
85 lines (76 loc) · 3.28 KB
/
the-skyline-problem.py
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
74
75
76
77
78
79
80
81
82
83
84
# Time: O(nlogn)
# Space: O(n)
start, end, height = 0, 1, 2
class Solution(object):
# @param {integer[][]} buildings
# @return {integer[][]}
def getSkyline(self, buildings):
intervals = self.ComputeSkylineInInterval(buildings, 0, len(buildings))
res = []
last_end = -1
for interval in intervals:
if last_end != -1 and last_end < interval[start]:
res.append([last_end, 0])
res.append([interval[start], interval[height]])
last_end = interval[end]
if last_end != -1:
res.append([last_end, 0])
return res
# Divide and Conquer.
def ComputeSkylineInInterval(self, buildings, left_endpoint, right_endpoint):
if right_endpoint - left_endpoint <= 1:
return buildings[left_endpoint:right_endpoint]
mid = left_endpoint + ((right_endpoint - left_endpoint) / 2)
left_skyline = self.ComputeSkylineInInterval(buildings, left_endpoint, mid)
right_skyline = self.ComputeSkylineInInterval(buildings, mid, right_endpoint)
return self.MergeSkylines(left_skyline, right_skyline)
# Merge Sort.
def MergeSkylines(self, left_skyline, right_skyline):
i, j = 0, 0
merged = []
while i < len(left_skyline) and j < len(right_skyline):
if left_skyline[i][end] < right_skyline[j][start]:
merged.append(left_skyline[i])
i += 1
elif right_skyline[j][end] < left_skyline[i][start]:
merged.append(right_skyline[j])
j += 1
elif left_skyline[i][start] <= right_skyline[j][start]:
i, j = self.MergeIntersectSkylines(merged, left_skyline[i], i,\
right_skyline[j], j)
else: # left_skyline[i][start] > right_skyline[j][start].
j, i = self.MergeIntersectSkylines(merged, right_skyline[j], j, \
left_skyline[i], i)
# Insert the remaining skylines.
merged += left_skyline[i:]
merged += right_skyline[j:]
return merged
# a[start] <= b[start]
def MergeIntersectSkylines(self, merged, a, a_idx, b, b_idx):
if a[end] <= b[end]:
if a[height] > b[height]: # |aaa|
if b[end] != a[end]: # |abb|b
b[start] = a[end]
merged.append(a)
a_idx += 1
else: # aaa
b_idx += 1 # abb
elif a[height] == b[height]: # abb
b[start] = a[start] # abb
a_idx += 1
else: # a[height] < b[height].
if a[start] != b[start]: # bb
merged.append([a[start], b[start], a[height]]) # |a|bb
a_idx += 1
else: # a[end] > b[end].
if a[height] >= b[height]: # aaaa
b_idx += 1 # abba
else:
# |bb|
# |a||bb|a
if a[start] != b[start]:
merged.append([a[start], b[start], a[height]])
a[start] = b[end]
merged.append(b)
b_idx += 1
return a_idx, b_idx