It is natural to me that segment tree should be used here: let `min_x`

, `max_x`

be the minimal and maximal x-coordinates of the buildings, then we need to maintain the interval `[min_x, max_x+1)`

. I use `max_x+1`

only because this will take care of the last point that should be included in the answer. For each building `[x, y, h]`

, we need to update interval `[x, y)`

with height `h`

.

You can see my code for definition of the segment node `Node`

.

```
class Node(object):
'''
Node definition for segment trees
'''
def __init__(self, b=0, e=0, x=0):
# children
self.left = None
self.right = None
# interval
self.begin = b
self.end = e
# max value of the height within this interval
self.val = x
# whether is a whole interval
self.whole = True
def update(self, l, r, h):
if self.begin >= r or self.end <= l:
return
if l <= self.begin and self.end <= r and h >= self.val:
self.val = h
self.whole = True
if self.left:
self.left.update(l, r, h)
self.right.update(l, r, h)
return
if self.whole and h <= self.val:
return
self.create_children()
self.left.update(l, r, h)
self.right.update(l, r, h)
self.val = max(self.val, h)
self.whole = False
def create_children(self):
if self.left:
return
b, e = self.begin, self.end
m = (b + e) / 2
self.left = Node(b, m, self.val)
self.right = Node(m, e, self.val)
def collect(self, ans):
if self.whole:
if len(ans) == 0:
ans.append([self.begin, self.val])
return
_, h = ans[-1]
if h == self.val:
return
ans.append([self.begin, self.val])
else:
self.left.collect(ans)
self.right.collect(ans)
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
n = len(buildings)
if n == 0:
return []
min_x = buildings[0][0]
max_x = max(b[1] for b in buildings)
tree = Node(min_x, max_x + 1)
for l, r, h in buildings:
tree.update(l, r, h)
ans = []
tree.collect(ans)
return ans
```

Before I describe my confusion, let me say a word about `self.whole`

. It is a boolean value indicating whether the interval is split into intervals with different heights. My confusion is in the method `update`

. My original idea of `update`

goes like:

- If the building is outside the range of the interval, return directly
- If the building covers the whole interval and the building's height is bigger than or equal to current height of the interval, update the interval and make it a whole interval, return
- If the interval is a whole interval and the height of the building is less than or equal to current height of the interval, return directly again
- Split the interval into two, update these smaller intervals, update the maximal height of the interval, and mark the current interval not a whole interval.

However, it turns out that the above idea is not correct. In step 2), before return, I need also to update the children! I don't understand why I have to update the children immediately. I thought I can wait until a taller building comes, I then update them with data from this taller building. I need help to clear this confusion.

Some thoughts on optimization: The time complexity is `O(nlog(max_x-min_x))`

. If `max_x-min_x`

is much bigger than `n`

, it worths to remap the x-coordinates of the buildings to 0, 1, ..., n. Then the time complexity becomes `O(nlogn)`

.

One thing to add: The correctness of the algorithm above relies on the fact that for each building `[x, y, h]`

, we always have `x < y`

. This means my code will fail this test case: `[[1, 1, 1]]`

.