Customer Support: email@example.com
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
- If you are a student, email to firstname.lastname@example.org to get special student discount.
In this chapter, we will learn how to compute the Union of overlapping rectangles in 2-D plane with all their base (lower horizontal boundary line) at the same y-coordinate first.
We will discuss the concept here by solving Skyline problem. We will see how we can effectively leverage Sweep Line technique to solve this kind of problems.
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance
Now suppose you are given the x-coordinates and heights of all the buildings as shown on the left side of the image below. Our objective is to think through and come up with an algorithm to output the skyline formed by these buildings collectively, as shown on the right side of the image below.
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in the image below could be represented as: [[2,9,10], [3,6,15], [5,12,12], [13,16,10], [13,16,10], [15,17,5]] .
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour. For instance, the output skyline for the image below should be represented as: [[2,10], [3,15], [6,12], [12,0], [13,10], [16,5], [17,0]]
Solution:My thought process about this problem is as follows:
Let's think about some of the very simple and trivial cases as I have drawn in the image above. Most of the images in this site will be hand-drawn to give you an impression of whiteboarding. Whiteboarding and pen-n-paper are the real-world ways of brainstorming and coming to a solution.
Case#1 alone gives a lot of insightful data. If a wider building exists in front or behind a less wide building, the wider building will overshadow the less wide building in the output skyline. Put in a different way, if a building (say, b1) which has not ended yet has height higher than the building (say, b2) we are trying to process, and if this building ends before the former building (b1) ends, then none of the start and end line of b2 would be part of the skyline.
From case #2 we observe if a higher start line has already been found, and the building to which it belongs is still current (i.e, the building has not ended yet), then the start of a building with lower height does not become part of the skyline
From case #3 we observe if a higher start line has already been found, and the building to which it belongs is still current (i.e, the building has not ended yet), then the end of a building with lower height does not become part of the skyline.
From case #4 we observe that if a building with lower height starts before a building with higher height and ends after the later then both the start and end of both the buildings will be part fo the skyline.
There are many more cases that someone can come up with, but these four are the simplest and most common ones and are most likely to come up in someone's mind instantly after reading the problem statement. And, guess what? These 4 cases give us enough information to design the core of our algorithm.
My observations from the above 4 cases:
All 4 cases have some thing in common and that is : The start of a building and its height are of immense importance.
We are doing majority of the decision-taking based on when (or, where) a building has started.
We definitely need to track the beginnings and heights of the buildings as we process them.
- We are scanning the buildings from left to right. Our whole discussion so far has been revolving around that. And this came naturally. You do not need to know the algorithm from beforehand to decipher that.
What about the endings of the buildings ? Depending on the max height of all the buildings which are current (i.e, which we are currently
processing and are not done processing), the end line of a building either becomes part of the skyline or it doesn't.
If you think carefully, you would be able to convince yourself that an end line becomes part of the skyline only if it is the highest building of all the active building. Active buildings = buildings for which we haven't processed their end lines yet.
- The comment in the above point applies for stat lines (beginnings) of the buildings as well. A start line of a building also becomes part of the skyline only if the height of this building is higher than the height of all the buildings we are currently processing, i.e, only if this building becomes the new tallest building (local maxima).
From above observation let's jot down few important points in order to design our algorithms:
We definitely need to sort the buildings in ascending order. We actually need the start lines and end lines of the
buildings to be sorted.
- What happens when more than one building start at the same location ? Whose start line should come first ?
- What happens when more than one building ends at the same location ? Whose end line should come first ?
- What happens when one building starts where another ends ?
To answer the above 3 questions we would need to draw how the buildings would look in such scenarios. Let's look at the image below:
As we can see from the diagram above,
When more than one building starts at the same location, if we process the shorter building first
we would get an unnecessary point, which is not a key point.
So, for any two buildings with same starting location, process the taller building first. Reason: Let's suppose so far the tallest building we have is shorter than both the buildings we are trying to process. This is important to demonstrate the core concept here.
If we process the start line of the shorter building first, since this would be taller than the heights of all other buildings, then the x-y coordinates of the top end of the building would be added.
Now when we process the start line of the taller building, the coordinates of the top end of the start line of the taller building is also added. And now there we have the problem. Whereas the later one is perfectly fine, the former one is not, as you can see from the diagram. To avoid this we need to process the start line of the taller building first.
For any two buildings ending at the same location, process the end line of the shorter building first. Because,
we are trying to avoid the unwanted top end of the end line of the shorter building in the skyline.
If we process the end line of the taller building first, after removing the height of this building, the shorter building might become the new tallest building. This will add the top end of the end line of the shorter building to the skyline, which is not what we want. This will not be a key point.
Similarly, when we have start line of a building and end line of another one locating at the same x coordinate,
we should process the start line before processing the end line irrespective of which building is taller.
If we process the end line first, then we will get the intersection point of this end line and the horizontal roof line of the current tallest building, and this point is not going to be a key point when the height of the tallest building, after the building to which the end line belongs is removed is shorter than the height of the building to which the start line belong and this is exactly what should be avoided. This is why start line needs to be processed first. Because if we process the start line first, when we process the end line we will get the intersection point of the vertical end line and horizontal roof line of the new tallest building. And this really matters when the building to which the start line belongs happens to be the new tallest building. Because in this case if we process the end line first we will get wrong answer. (Refer to 3a and 3b in the diagram)
Whenever we process a new building, track its height. And based on all the tracked heights so far
add the x-y coordinate of the top end of the start line in the skyline. If the height of the new building
is higher than all other buildings we are currently processing, add the x-y coordinate of the top end of the start line to
skyline. Otherwise ignore.
Same goes for the end lines. If the height of the building to which this end line belongs is higher than all other buildings we are currently processing, add the x-y coordinate of the top end of the end line to skyline. Otherwise ignore.
Once we process end line for a building, this building is no longer considered active. Remove this building from
the data structure.
After removing the end line let's suppose height h1 becomes the max height in the max heap. Let's say h1 belongs to a building b1.
Add the intersection of the vertical end line and the horizontal roof line of building b1 to the skyline.
- Sort the start lines and the end lines of the given buildings.
Iterate over the sorted list of start lines and end lines and do the following:
- From all the above discussion, MAX HEAP looks like a good candidate for this problem. We need to track the max height of all the active building at all time.
Whenever a new building is encountered (i.e, we encounter start line of an unprocessed building), see if the max height present in the max heap's
head is lower than the
height of the building we are trying to process.
If yes, put the x-y coordinate of the top end of the start line of the
building in the output data structure.
Now put the height of this building in the heap. This makes the building active.
When you encounter an end line check if it's height is same as the height on the head of the max heap. If yes,
add the x-y coordinate of the end line to the output data structure.
Now remove the height of the end line. This marks the building to which the end line belongs as processed.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Time Complexity:If there are n number of buildings, then there are 2n vertical lines (start line and end line) we need to process.
Sorting is O(2nlog2n) = O(nlogn).
Insertion and deletion from a heap are O(logn) operations. For 2n elements we have O(nlogn).
Overall time complexity = O(nlogn) + O(nlogn) = O(nlogn).