[LeetCode] 218. The Skyline Problem

218. The Skyline Problem

Hard

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

• lefti is the x coordinate of the left edge of the ith building.
• righti is the x coordinate of the right edge of the ith building.
• heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

Note: 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],...]

 

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

 

Constraints:

• 1 <= buildings.length <= 104
• 0 <= lefti < righti <= 231 - 1
• 1 <= heighti <= 231 - 1
• buildings is sorted by lefti in non-decreasing order.

---

문제 풀이

• 빌딩의 x 좌표와 y 좌표들이 주어진다.
• 건물이 겹칠 수도 있고, 떨어질 수도 있다.
• 빌딩의 개수는 최대 10^4 가 될 수 있다, 이는 Brute Force 를 사용할 수 있다는 뜻이기도하다.
• 건물들의 외각선을 땄을 때 한 그룹의 건물에서, 항상 앞쪽의 가장 높은 첫 좌표 (x, y) 를 추출하고, 외각선 그룹의 가장 마지막 끝좌표를 포함해야한다. 
• 즉 높이가 달라지는 가장 왼쪽 좌표와 끝나는 마지막 좌표가 필요하다.
  • Heap 사용
    • 모든 건물의 x 좌표와 인덱스를 저장하여 정렬한다, 이는 x 좌표를 기준으로 먼저 정렬되고 그 다음 좌표의 인덱스를 기준으로 정렬된다. 
    • 정렬된 좌표들을 시작으로, 첫 좌표인지 끝 좌표인지 구별해야한다.
    • 만약 첫 좌표이면 끝 좌표를 힙에 높이와 끝 좌표를 같이 넣는다, 이때 높이가 내림차순으로 힙에 정렬이 되어야한다. 
      (-1 을 곱해서 힙에 넣으면 다른 처리없이 내림차순 힙을 사용할 수 있음)
    • 만약 힙에 들어가있는 오른쪽 좌표 중에 가장 높이가 큰 좌표는 현재 x 좌표보다 작거나 같다면 필요가 없기 때문에 계속해서 heap pop 해준다. 
      (현재 x 좌표보다 작거나 같다면 이미 처리되었기 때문)
    • 이를 첫좌표가 현재 x 좌표랑 같을때 까지 반복하는데, 첫 시작점이 같으나 끝 점이 다른 건물이 중복해서 생성될 수 있기 때문이다. 
    • 그리고 끝점을 넣은 힙에서 최대값을 구하는데, 이는 현재 위치에서 가장 높은 건물의 값이 존재할때 여러 건물들 중에 가장 높은 건물의 높이를 구하기 위함이다.
    • 반대로 끝점을 담은 힙에 아무것도 없다면, 현재 위치에서 건물들의 그룹은 존재하지 않는다.
    • 답에 처음 좌표는 무조건 넣어주고, 그 다음 부터 최대 값과 정답의 가장 마지막 높이를 비교해서 다르다면 답으로 넣는다. 
      (같은 높이의 건물들이 여러개 들어왔을때, 첫 왼쪽 꼭대기와 가장 마지막 오른쪽 아래 좌표를 중복되지 않게 넣어야되기 때문)

소스 코드

Heap

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        edges = []
        for i, build in enumerate(buildings):
            edges.append([build[0], i])
            edges.append([build[1], i])
        edges.sort()
        
        live, answer = [], []
        idx = 0
        
        while idx < len(edges):
            curr_x = edges[idx][0]
            
            while idx < len(edges) and edges[idx][0] == curr_x:
                b = edges[idx][1]
                if buildings[b][0] == curr_x:
                    right = buildings[b][1]
                    height = buildings[b][2]
                    heapq.heappush(live, [-height, right])

                while live and live[0][1] <= curr_x:
                    heapq.heappop(live)
                idx += 1
            
            max_height = -live[0][0] if live else 0
            
            if not answer or max_height != answer[-1][1]:
                answer.append([curr_x, max_height])
        
        return answer