# Segment tree, accepted with confusion

• 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:

1. If the building is outside the range of the interval, return directly
2. 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
3. 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
4. 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]]`.

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