Segment tree, accepted with confusion


  • 0
    R

    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]].


Log in to reply
 

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