The Skyline Problem

Problem: The Skyline Problem

What we care for is what height can be assigned to each index. So first we sort all left indexes and right indexes in a same set. Then we try to assign height from very first one. We use a heap to maintain heights of buildings before current position. If the building finishes before p, then we don't need to consider it. Then we extract the highest effective building from the heap and assign the height to current position if the height changes. If no previous heights, which means all previous buildings are finished, we can assign 0 to this position.

Code in Python:

import heapq

class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        res = [[-1, 0]]
        n = len(buildings)

        def add(position, height):
            if res[-1][-1] != height: res.append([position, height])

        positions = set([building[0] for building in buildings] + [building[1] for building in buildings])
        heap = []

        i = 0
        for p in sorted(positions):
            while i < n and buildings[i][0] <= p:
                heapq.heappush(heap, (-buildings[i][2], buildings[i][1]))
                i += 1
            while heap and heap[0][1] <= p:
                heapq.heappop(heap)
            height = -heap[0][0] if heap else 0
            add(p, height)
        return res[1:]