{x}
blog image

The Skyline Problem

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.

Solution Explanation:

The Skyline Problem aims to find the silhouette of buildings when viewed from a distance. The input is a list of buildings, each represented as [left, right, height]. The output is a list of key points [[x1, y1], [x2, y2], ...], representing the skyline's contour. Crucially, consecutive points with the same height should be merged.

Approach: Line Sweep Algorithm with Priority Queue

The most efficient approach uses a line sweep algorithm combined with a priority queue. Here's a breakdown:

  1. Event Points: Identify all significant x-coordinates (left and right edges of buildings) and sort them. These are the event points where the skyline might change.

  2. Priority Queue (Max Heap): Maintain a priority queue (max heap) to track the heights of currently active buildings. The heap stores (-height, right) tuples. We use negative height because max heaps prioritize larger values, and we want the tallest building to be at the top.

  3. Sweep: Iterate through the sorted event points:

    • Left Edge: When encountering a building's left edge, add its height to the priority queue.
    • Right Edge: When encountering a building's right edge, remove its height from the priority queue.

    After processing each event point:

    • Check the maximum height in the priority queue (top element of the heap).
    • If the maximum height is different from the previous maximum height, add the current event point and the maximum height as a key point to the result.

  4. Output: The result is a list of [x, height] pairs representing the skyline, with consecutive points of the same height merged.

Time Complexity Analysis:

  • Sorting the event points takes O(M log M) time, where M is the number of event points (at most twice the number of buildings).
  • Iterating through the event points takes O(M) time.
  • Priority queue operations (insert and delete) take O(log N) time each, where N is the maximum number of buildings active at any time. In the worst case, N could be equal to the total number of buildings.
  • Overall, the dominant factor is the sorting, leading to a time complexity of O(M log M), where M is approximately 2 * the number of buildings.

Space Complexity Analysis:

  • The priority queue requires O(N) space, where N is the maximum number of active buildings.
  • The sorted event points list takes O(M) space.
  • The resulting skyline list takes O(M) space in the worst case.
  • Therefore, the overall space complexity is O(M), where M is approximately 2 * the number of buildings.

Code Examples (Python, C++, Go, Rust):

The provided code snippets implement this line sweep algorithm with a priority queue (or equivalent data structure in different languages). Note the slight variations in implementation detail based on the language's features, such as how the priority queue is implemented (using PriorityQueue in Python, std::priority_queue in C++, container/heap in Go, and BinaryHeap in Rust). The core algorithm, however, remains consistent.