218.The Skyline Problem

Tags: [sort], [merge], [merge_sort], [divide_conquer]

Com: {fb}, {g}

Link: https://leetcode.com/problems/the-skyline-problem/#/description

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).The geometric information of each building is represented by a triplet of integers[Li, Ri, Hi], where Liand Riare the x coordinates of the left and right edge of the ith building, respectively, and Hiis its height. It is guaranteed that0 ≤ Li, Ri ≤ INT_MAX,0 < Hi ≤ INT_MAX, andRi - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as:[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of "key points" (red dots in Figure B) in the format of[ [x1,y1], [x2, y2], [x3, y3], ... ]that uniquely defines a skyline.A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range[0, 10000].
• The input list is already sorted in ascending order by the left x positionLi.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance,[...[2 3], [4 5], [7 5], [11 5], [12 7]...]is not acceptable; the three lines of height 5 should be merged into one in the final output as such:[...[2 3], [4 5], [12 7], ...]

Better Solution: Divide And Conquer

class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        if not buildings:
            return []

        return self.get_skyline_helper(buildings, 0, len(buildings) - 1)

    def get_skyline_helper(self, buildings, start, end):
        # base case
        if start == end:
            building = buildings[start]
            result = [[building[0], building[2]], [building[1], 0]]
            return result

        mid = start + (end - start) / 2
        left_skylines = self.get_skyline_helper(buildings, start, mid)
        right_skylines = self.get_skyline_helper(buildings, mid + 1, end)

        return self.merge(left_skylines, right_skylines)

    def merge(self, left_skylines, right_skylines):
        result = []

        left_h = 0
        right_h = 0

        left_index = 0
        right_index = 0
        x = 0
        h = 0
        while left_index < len(left_skylines) and right_index < len(right_skylines):
            if left_skylines[left_index][0] < right_skylines[right_index][0]:
                x = left_skylines[left_index][0]
                left_h = left_skylines[left_index][1]
                h = max(left_h, right_h)
                left_index += 1

            elif left_skylines[left_index][0] > right_skylines[right_index][0]:
                x = right_skylines[right_index][0]
                right_h = right_skylines[right_index][1]
                h = max(left_h, right_h)
                right_index += 1

            else:
                x = left_skylines[left_index][0]
                left_h = left_skylines[left_index][1]
                right_h = right_skylines[right_index][1]
                h = max(left_h, right_h)
                left_index += 1
                right_index += 1

            if not result or result[-1][1] != h:
                result.append([x, h])

        while left_index < len(left_skylines):
            if not result or result[-1][1] != left_skylines[left_index][1]:
                result.append([left_skylines[left_index][0], left_skylines[left_index][1]])
            left_index += 1

        while right_index < len(right_skylines):
            if not result or result[-1][1] != right_skylines[right_index][1]:
                result.append([right_skylines[right_index][0], right_skylines[right_index][1]])
            right_index += 1

        return result

Revelation:

• I think when we deal with the remaining left_skylines and the remaining the right_skylines, we still need to check the last element in the result.

Note:

• Time complexity = O(nlgn), n is the number of elements in buildings, like the merge sort, the divide take T = O(lgn), but each time dividing has a merge, and the merge takes T = O(n), so the total T = O(nlgn).

Solution: Divide And Conquer

class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        if not buildings:
            return []

        return self.get_skyline_helper(buildings, 0, len(buildings) - 1)

    def get_skyline_helper(self, buildings, left, right):
        # base case
        if left > right:
            return []
        if left == right:
            result = [[buildings[left][0], buildings[left][2]],
                      [buildings[left][1], 0]]
            return result

        mid = left + (right - left) / 2
        left_skyline = self.get_skyline_helper(buildings, left, mid)
        right_skyline = self.get_skyline_helper(buildings, mid + 1, right)

        return self.merge_skylines(left_skyline, right_skyline)

    def merge_skylines(self, left_skyline, right_skyline):
        left_index = 0
        right_index = 0
        left_height = 0
        right_height = 0

        result = []
        while left_index < len(left_skyline) and right_index < len(right_skyline):
            pos = 0
            height = 0
            if left_skyline[left_index][0] < right_skyline[right_index][0]:
                pos = left_skyline[left_index][0]
                left_height = left_skyline[left_index][1]
                height = max(left_height, right_height)
                left_index += 1

            elif left_skyline[left_index][0] > right_skyline[right_index][0]:
                pos = right_skyline[right_index][0]
                right_height = right_skyline[right_index][1]
                height = max(left_height, right_height)
                right_index += 1

            else:
                pos = left_skyline[left_index][0]
                left_height = left_skyline[left_index][1]
                right_height = right_skyline[right_index][1]
                height = max(left_height, right_height)
                left_index += 1
                right_index += 1

            if not result or result[-1][1] != height:
                result.append([pos, height])

        result += left_skyline[left_index:]
        result += right_skyline[right_index:]

        return result

Revelation:

• The key function here is the 'merge_skylines()' function. Think about if we have two skylines one from left, and the other from right, how do we merge these two skylines. There are several cases:
• From the above cases, we can see why we declare the 'left_height' and 'right_height' out of the loop, to cache the previous heights.

Note:

• Time complexity = O(nlgn), there are O(lgn) times 'divide'. After each time divide there is a conquer, each conquer will do 'merge_skylines()' which will take O(n). n is the number of buildings.