It is natural to me that segment tree should be used here: let
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
You can see my code for definition of the segment 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 max_x = max(b 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
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
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]].