Last Updated: 19 Mar, 2021
The Skyline Problem
Hard
Asked in companies
You are given 'N' rectangular buildings in a 2-dimensional city. Your task is to compute the skyline of these buildings, eliminating hidden lines return the skyline formed by these buildings collectively. A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. The geometric information of each building is given in the array of buildings where BUILDINGS[i] = [LEFT_i, RIGHT_i, HEIGHT_i]:
-> LEFT_i is the x coordinate of the left edge of the ith building.
-> RIGHT_i is the x coordinate of the right edge of the ith building.
-> HEIGHT_i 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],...].
Also, the buildings are sorted by a non-decreasing order.
For more clarification see sample case 1.
Input Format:
The first line of input contains a single integer ‘N’ denoting the number of buildings that would be given.
And the rest of the ‘N’ lines contain three space-separated integers: Left and right Indices of the vertical edges of the building while the last integer represents the height of the building ‘H’.
Output Format :
Return the list of skylines formed by these buildings collectively.
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 on the left.
The 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 is where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= | BUILDINGS | <= 10^4
0 <= LEFT_i < RIGHT_i <= 2^31 - 1
1 <= HEIGHT_i <= 2^31 - 1
Time Limit: 1 sec
Approaches
The idea here is to first, sort the critical POINTS with respect to their coordinate and height pairs. Make a pair of 'X1' and take a negative of the height for the building so that 'X1' pairs are sorted before 'X2' pairs. Create a dictionary keeping the heights as keys and as soon as a left edge of a building is encountered, we add that building to the dictionary with its height as the key. When we encounter the right edge of a building, we remove that from the dictionary. When you hit the left edge of a building you add it to the dictionary, and when you hit the right edge of a building you delete the key. Finally, any time we encounter a critical point, after updating the dictionary we find the height of that critical point with maximum height value from keys that we already have in the dictionary to the value peeked from the top of the heap.
The algorithm will be-
- Store the coordinates and heights of the buildings paired up with each other with the first building coordinate paired after taking negative of the height and the second coordinate with positive height in a list ‘POINTS’.
- Now, sort edges present in the ‘POINTS’ list (array) in ascending order.
- The positions are now sorted from left to right, small to large. Now, initialise a dictionary named 'HEIGHTS' with zero as its first key, having a value of 1 since this would be the last height that would be added.
- Now, for each pair of an edge in the ‘POINTS’ list (array) and check:
- Update the dictionary if the current edge is a start edge (with negative height) increment the value of the key by 1.
- Delete the invalid buildings from the dictionary if an end edge is encountered for a key after decrementing its value by 1.
- Now, In each iteration update the 'SKYLINE', which records the highest building from some position, and add it to the final list of our 'SKYLINE's if the current highest is no longer the tail of the 'SKYLINE' (previous highest).
- We finally return the 'SKYLINE' list (array) that we have formed.
The idea here is to first, sort the critical points. Then scan across the critical points from left to right. When we encounter the left edge of a rectangle, we add that rectangle to the heap with its height as the key. When we encounter the right edge of a rectangle, we remove that rectangle from the heap. As you scan, when you hit the left edge of a building you add it to the heap, and when you hit the right edge of a building you pop nodes off the top of the heap repeatedly until the top node is a building whose right edge is still ahead. With this strategy, your heap may contain buildings that have already ended, but it doesn’t matter because you’ll discard them as soon as they’re at the top of the heap. Finally, any time we encounter a critical point, after updating the heap we set the height of that critical point to the value peeked from the top of the heap.
The algorithm will be-
- Sort edges with [POSITION, -HEIGHT, VALID_UNTIL]. Here, the first two elements are for iterating edges with the correct sequence, while, the last one is for popping out invalid buildings during the iteration.
- The positions are now sorted from left to right, small to large.
- When positions are overlapped, sort the height from high to low, large to a small image
- Now, for each edge:
- Pop-out invalid buildings from the top of the heap (there might still exist invalid ones in the heap, but we just want to make sure the top of the heap is valid).
- And update the heap if the current edge is a start edge
- In each iteration update the 'SKYLINE', which records the highest building from some position, if the current highest is no longer the tail of the 'SKYLINE' (previous highest).
- We finally return the 'SKYLINE' list (array) that we have formed.
Similar problems