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


  • 3
    J

    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]

Log in to reply
 

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