218.The Skyline Problem

In [3]:

import heapq, sys
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time
from typing import List
INF = 1e20

In [5]:

class Solution1(object):
    @logging_time
    def getSkyline(self, buildings: List[List[int]]):
        def func(s, e):
            if s == e:
                l, r, h = buildings[s]
                return [[l, h], [r, 0]]
            mid = (s + e) // 2
            left = func(s, mid)
            right = func(mid + 1, e)

            def merge(left, right):
                """ left and right are skyline. """
                h1 = h2 = i = j = 0
                n1, n2 = len(left), len(right)
                left.append([INF, 0])
                right.append([INF, 0])
                cross = []

                def append(x, strip):
                    """ append a strip to x
                    :type x: 2D list with size [[2]*]
                    :rtype: 1D list with size 2
                    """
                    # # Check for redundant strip, a strip is redundant if it has same height or left as previous
                    if len(x) > 0 and x[-1][1] == strip[1]: # height is same
                        return
                    elif len(x) > 0 and x[-1][0] == strip[0]:  # left is same
                        x[-1][1] = max(x[-1][1], strip[1])
                        return
                    # general case
                    x.append(strip)

                for _ in range(n1 + n2):
                    if left[i][0] < right[j][0]:
                        h1 = left[i][1]
                        append(cross, [left[i][0], max(h1, h2)])
                        i += 1
                    else:
                        h2 = right[j][1]
                        append(cross, [right[j][0], max(h1, h2)])
                        j += 1
                cross[-1][1] = 0  # end's height is always 0
                return cross

            return merge(left, right)
        return func(0, len(buildings) - 1)

sol1 = Solution1()

In [7]:

buildings = [[1,2,1],[1,2,2],[1,2,3]]
# buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
print("answer:", sol1.getSkyline(buildings, verbose=True))

WorkingTime[getSkyline]: 0.04101 ms
answer: [[1, 3], [2, 0]]

In [13]:

class Solution2(object):
    @logging_time
    def getSkyline(self, buildings: List[List[int]]):
        # sort by (L, -H, R) increasing order
        # end building events 도 넣는다.
        events = sorted([(L, -H, R) for L, R, H in buildings] + list({(R, 0, 0) for _, R, _ in buildings}))
        # print(events)
        res, hp = [[0, 0]], [(0, 1e20)]  # dummy 값들
        # intuition
        # 1, pop buildings that are already ended
        # 2, if it's the start-building event, make the building alive
        # 3, if previous keypoint height != current highest height, edit the result
        for x, negH, R in events:
            while x >= hp[0][1]:
                heapq.heappop(hp)
            if negH:
                heapq.heappush(hp, (negH, R))
            if res[-1][1] + hp[0][0]:
                res.append([x, -hp[0][0]])
        return res[1:]

sol = Solution2()

In [14]:

sol.getSkyline(buildings, verbose=True)

WorkingTime[getSkyline]: 0.03839 ms

[[1, 3], [2, 0]]