Given n buildings on a two-dimensional plane, find the skyline of these buildings.
Each building on the two-dimensional plane has a start and end x-coordinates, and a y-coordinate height. Skyline is defined as a unique representation of rectangular strips of different heights which are created after the overlap of multiple buildings on a two-dimensional plane.
The following picture demonstrates some buildings on the left side and their skyline on the right.
2 9 10
3 7 15
5 12 12
15 20 10
19 24 8
From the image referenced above, we see the blue building at the start and the corresponding red dot in the right image at (2,10). The next change in skyline occurs at an x coordinate of 3 with the red building coming up at the height of 15, so in the output, the next line is printed as 3 15. Similarly, all the buildings are traversed to find the output as given in the sample output section.
Input Parameters: The input of buildings is given in a two-dimensional integer array format. The outer array contains multiple buildings where each building is an array of integers of size 3. The first integer represents the start coordinate of the building, the second integer represents the end coordinate of the building and the third integer represents its height.
Output: Return a two-dimensional integer array. The outer array has different rectangular strips, each element is an array of size two. The first element in the inner array is the x coordinate of the strip and the second element is the y coordinate of the strip (red dots in the image above).
A BuildingIndex class is defined in the solution consisting of three members:
A priority queue named priorityQ is created. All the start and end points of all the buildings as objects of BuildingIndex class are added in this queue with the following insertion constraints:
A binary search tree named heightCountQ is created which stores the count of heights ordered by the heights of buildings.
Also, a variable named maxHeight is initialized with 0 which stores the current max height of the skyline.
Now pop elements from the priorityQ, one by one, till it is empty.
Sorting all the buildings as per the given constraints in the description would take O(2n*log(2n)), where n is the number of buildings in the given array and 2*n is the BuildingIndex. Also maintaining the count of heights take O(n*log(n)), since each insertion and deletion is O(log(n)) in a BST.
So, the total time complexity is O(n*log(n)).
Auxiliary Space Used:
The priorityQ and heightCount both require O(n) auxiliary space to store n buildings. So, total auxiliary space complexity is O(n).
Input and output arrays both require 3*n and 2*n amount of space respectively. Total space complexity including auxiliary space comes out to be O(n).