Problem Description

In this problem, we are given a set of buildings in a city and are asked to compute the city's skyline. A skyline is essentially the outer contour created by all the buildings when viewed from a distance. Each building is represented by three integers, the x-coordinate of its left edge (left), the x-coordinate of its right edge (right), and its height (height). The aim is to return a list of all 'key points' that outline this contour.

A 'key point' is an x-coordinate paired with a height (y-coordinate), where there is a change in the skyline's height. These points are collected into a list where each element has the form [x, y] and represents the start of a new horizontal line in the skyline. The last point in the list always ends with a height of 0, indicating the end of the skyline to the rightmost building's end.

The result must be sorted by the x-coordinate, and it cannot contain consecutive horizontal lines of the same height. Instead, such lines should be merged into a single line.

Intuition

The intuition behind the solution is to process all buildings and simulate the construction of the skyline by bracketing the start and end of each building's influence on the skyline. A priority queue is used to keep track of the tallest building that's currently affecting the skyline since that will determine the outer contour at any point.

1. Collecting Edges: Gather all the possible "edge" positions from the buildings' start and end points. These are the candidates for where the skyline could possibly change.

2. Sorting Edges: By sorting the edges, we are simulating the horizontal scanline moving from left to right across the city.

3. Using a Priority Queue: As we pass each edge, we use a priority queue to add buildings when we cross their start point and remove them when we cross their end point. The priority queue always keeps the highest building at the top, so we can easily find out which building defines the sky at a given edge.

4. Updating the Skyline: While going through the edges, we check if the current max height changes after adding or removing buildings from our priority queue. If there is a change in height, this represents a key point in our skyline, and we record it. We also make sure to skip any consecutive edges of the same height to satisfy the condition of no consecutive horizontal lines with equal height.

5. Building the Output: The key points are added to the skys list, which becomes our final answer representing the entire skyline as per the problem's requirements.

By processing the edges in sorted order and updating the priority queue, we efficiently calculate the key points of the skyline without having to simulate every possible x-coordinate, which would be less efficient.

Learn more about Segment Tree, Divide and Conquer, Line Sweep and Heap (Priority Queue) patterns.

Solution Approach

The solution follows a step-by-step approach using data structures like Priority Queue and list manipulation. Here's a breakdown of the key stages of the implementation:

1. Initializing Data Structures: A list skys is initialized to hold the resultant skyline's key points. A separate list lines is used to collect all potential x-coordinates (both left and right edges of all buildings). A Priority Queue pq is used to store buildings currently part of the skyline. Each building is stored as a tuple (-height, left, right) in the priority queue to keep the tallest buildings at the top (as Priority Queue in Python is a min-heap, we store the height as negative to simulate a max-heap).

2. Sorting the Edges: The lines array is sorted to prepare for a left-to-right scan across all potential key points.

3. Processing Buildings: A while-loop is used to process all x-coordinates one by one in lines. Nested loops are then used to manipulate the priority queue as follows:

   • A loop adds buildings to the queue that start at or before the current line (x-coordinate), effectively saying that they now contribute to the skyline.
   • Another loop removes buildings from the queue whose right edge is at or before the current line, meaning they no longer contribute to the skyline.

4. Determining the Current Height: After buildings are added or removed, the height of the current skyline is determined by the top element's height in the priority queue. If the priority queue is empty, this height is 0.

5. Updating the Skyline: Before adding a new key point to skys, the algorithm checks whether the current height is the same as the last recorded height to avoid consecutive horizontal lines of the same height. If the height is different, a new key point [line, height] is appended to skys.

6. Edge Cases Handling: The uniqueness of key points is maintained by only adding a new key point when the height differs from the previous key point. This automatically handles edge cases and ensures no consecutive horizontal lines of equal height as prescribed by the problem statement.

In summary, by employing a scanning line algorithm that steps through the sorted x-coordinates and a max-heap implemented by a priority queue to keep track of the tallest building(s) influencing the skyline, this solution approach efficiently constructs the skyline by dynamically determining the key points where the contour changes.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following set of buildings represented as [left, right, height] tuples:

Buildings: [(1, 5, 11), (2, 7, 6), (3, 9, 13), (12, 16, 7), (14, 25, 3)]

1. Initializing Data Structures: We initialize skys to an empty list, lines to store potential x-coordinates, and pq as an empty Priority Queue.

2. Collecting Edges: We gather all edges from the buildings.

lines = [1, 5, 2, 7, 3, 9, 12, 16, 14, 25]

3. Sorting the Edges: We sort the edges.

lines = [1, 2, 3, 5, 7, 9, 12, 14, 16, 25]

4. Processing Buildings: We process each x-coordinate in lines.

   • We pass the x-coordinate 1 and add the building (1, 5, 11) to the priority queue.
   • Passing x-coordinate 2, we add the building (2, 7, 6) to the priority queue.
   • At x-coordinate 3, we add (3, 9, 13); the priority queue now has buildings with heights 11, 6, and 13 at the top.

5. Determining the Current Height: After the addition of buildings at x-coordinate 3, the height of the current skyline is from the top element of the priority queue, which is 13 (the height of the building at the top of the priority queue).

6. Updating the Skyline: Since 13 is the starting height of the skyline, our first key point is [1, 13]. As we pass through x-coordinates 5 and 7, buildings will be removed from the priority queue, possibly altering the height.

7. Continuing the Process: As we reach x-coordinate 9, the skyline is at height 0 since building (3, 9, 13) was the last to contribute and has now ended.

8. More Updates: As we move to x-coordinate 12, we add (12, 16, 7) to our priority queue, and since the height now changes from 0 to 7, a new key point [12, 7] is added to skys.

9. Edge Cases Handling: If at any point the current height is the same as the last recorded height, we do not add it to skys to avoid consecutive lines of the same height. For example, when building (14, 25, 3) starts at x-coordinate 14, the height does not change as it is less than the current height 7. So no new key point is added.

10. Completing the Skyline: The last key point will be [25, 0] as it indicates the end of the skyline with the height dropping back to 0 after building (14, 25, 3) ends.

The output for the skyline would be the skys list:

skys = [[1, 13], [9, 0], [12, 7], [16, 0], [25, 0]]

This list represents the changing points of the silhouette of the buildings when viewed from afar, without any redundant points, and it defines the skyline of the city according to the problem's statement.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of this code primarily comes from several operations: the sort operation on lines, the two while-loops that run within the for-loop iterating over lines, and the priority queue operations.

1. Sorting lines: Sorting an array has a time complexity of O(n log n), where n is the number of elements to sort. In the worst case, each building contributes two lines, so if we have k buildings, we will have 2k lines, leading to O(2k log(2k)) which simplifies to O(k log k).

2. First while-loop: This loop inserts buildings into the priority queue. Insertion into a priority queue (min-heap or max-heap) is O(log m), where m is the number of elements in the priority queue. In the worst case scenario, all k buildings might be inserted, leading to O(k log k).

3. Second while-loop: This loop removes buildings from the priority queue. The worst-case removal from a priority queue is also O(log m). However, this operation will be bounded by the number of buildings k, not the number of lines. So in the worst case, all k buildings might be removed, leading to a worst-case time complexity of O(k log k).

4. Priority queue operations: The call to pq.empty() is O(1), and accessing the top element using pq.queue[0] is also O(1). However, the pq.put() and pq.get() operations inside the while-loops have O(log k) complexity per operation, contributing to the overall complexity when considering the loop iterations.

Given that these operations are not nested but rather sequential, the total worst-case time complexity is the sum of the individual complexities: O(k log k + k log k + k log k), which simplifies to O(k log k).

Space Complexity

The space complexity is dictated by the space needed to store the lines, skys, and the contents of the priority queue pq.

1. Storing lines: We store at most 2k line starts and ends from k buildings, so the space needed for lines is O(k).

2. Storing skys: In the worst case, each line could result in a change in height, meaning the skys array could have as many as 2k entries, which is O(k).

3. Priority queue pq: The priority queue can hold at most k buildings at any given time, since that's the max number of buildings we have. So the space complexity is O(k) for the priority queue.

Adding these up, the space complexity of the algorithm is O(k + k + k) which simplifies to O(k).

Learn more about how to find time and space complexity quickly using problem constraints.