160ms Python solution, bottom-up, divide and conquer

• The idea is basically like the bottom-up merge sort. To use less code, a trick is used in the case where left.x == right.x.

``````def getSkyline(self, buildings):
if not buildings:
return []
def merge(left, right):
h1, h2 = 0, 0
ans, l, r =[], 0, 0
while l < len(left) and r < len(right):
lx, rx = left[l][0], right[r][0]
# Note how we handle lx == rx
if lx <= rx:
pos, h1 = left[l], left[l][1]
l += 1
if lx >= rx:
pos, h2 = right[r], right[r][1]
r += 1
pos[1] = max(h1, h2)
if ans and ans[-1][1] == pos[1]:
continue
ans.append(pos)

ans += left[l:] if l < len(left) else right[r:]
return ans

# Translate buildings into points.
buildings = [[[a, h], [b, 0]] for a, b, h in buildings]
while len(buildings) > 1:
buildings = [merge(buildings[2 * i], buildings[2 * i + 1])
for i in xrange(len(buildings) / 2)] + \
([buildings[-1]] if len(buildings) % 2 else [])
return buildings[0]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.