Algorithms
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. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
All buildings share common bottom and every building is represented by triplet (left, height, right)
‘left’: is x coordinated of left side
‘right’: is x coordinate of right side
‘height’: is height of building.
A skyline is a collection of rectangular strips. A rectangular strip is represented as a pair (left, height) where left is x coordinate of left side of strip and ht is height of strip.
For example,
Input: Array of buildings
{ (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) }
Output: Skyline (an array of rectangular strips)
A strip has x coordinate of left side and height
{ (1,11), (3,13), (9,0), (12,7), (16,3), (19,18), (22,3), (23,13), (29,0) }
How do we solve it? If we notice closely then we will see that the buildings form a range of intervals where some of them are overlapping with each other. We need to basically find strips such that if an interval overlaps at the left point of the strip then height of the strip would be the maximum height of all the overlapping ranges. So, the idea is to find overlapping intervals if we consider each building as an interval and the height of the building as the weight of the interval. Note that, I have discussed in a previous post about solving the problem of finding overlapping intervals and merging intervals etc. We are going to apply same technique here. So, I highly suggest to first read this post.
We can separate the left coordinates of the buildings in an array called start and sort it based on the left and the height (because if we have several buildings start from the same left then we want to take the tallest building). Similarly we separate right coordinates of the buildings in another array called end and sort it based on right.
Now, we will do a similar algorithm as we do to find overlapping intervals. We start scanning both start and end from left to right. If current start is less then prev end then it is part of the current overlap. Otherwise we find end of a set of overlapping intervals.
For each start and end points we will compute one strip as follows –
1. If start point of current interval is part of current overlap then
- the height of the strip for this start point is the maximum height seen so far in the overlap.
- we will use a max heap to maintain the max so far.
2. Otherwise, we have an end of current overlap with the current end point.
- So, we need to remove the height of this end point from the heap as the overlap ends here.
- The height of the strip for this end point is the maximum of the remaining buildings in current overlap.
For example, given buildings = { (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) }, the strips are constructed as follows –
(4) ______________
24 28
(13) ____________________
23 29
(13) __________________ (18) _________
3 9 19 22
(6) ______________ (3) __________________________________
2 7 14 25
(H=11) ____________ (7) ____________
1 5 12 16
...|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|....
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Now, we scan all the left and right points in the sorted order.
At coord=1, we have a start point and maximum height seen so far including current is 11. Heap state={11}. So, we construct a strip (1, 11).
At coord=2, we have a start point and so it is a part of current running overlapping interval. Maximum height seen so far including current height (=6) is 11. Heap state={11, 6}. So, we construct a strip (2, 11).
At coord=3, we have a start point and so it is a part of current running overlapping interval. Maximum height seen so far including current height (=13) is 13. Heap state={13, 11, 6}. So, we construct a strip (3, 13).
At coord=5, we have an end point and so this interval not anymore part of current running overlapping interval. We remove the height 11 of this interval from the heap. Heap state={13, 6}. Maximum height in the remaining intervals is 13. So, we construct a strip (5, 13).
At coord=7, we have an end point and so this interval not anymore part of current running overlapping interval. We remove the height 6 of this interval from the heap. Heap state={13}. Maximum height in the remaining intervals is 13. So, we construct a strip (7, 13).
At coord=9, we have an end point and so this interval not anymore part of current running overlapping interval. We remove the height 13 of this interval from the heap. Heap state={}. Maximum height in the remaining intervals is 0 (empty heap). So, we construct a strip (9, 0). At this point the current overlapping interval finishes.
At coord=12, we have a start point and as their is no current running interval so this is a start of a new running interval. Maximum height seen so far including current is 7. Heap state={7}. So, we construct a strip (12, 7).
Similarly, for rest of the intervals we constructs strips (14,7), (16,3), (19,18), (22,3), (23,13), (24,13), (28,13), (29,0).
All Strips = {(1,11), (2,11), (3,13), (5,13), (7,13), (9,0), (12,7), (14,7), (16,3), (19,18), (22,3), (23,13), (24,13), (28,13), (29,0)}
Finally we want to remove all the duplicate stripes – either the strips with same height in subsequent positions or strips ending at the same position for special case when we have many buildings ending at same right coordinate.
Removing duplicate strips -
{(1,11), (2,11), (3,13), (5,13), (7,13), (9,0), (12,7), (14,7), (16,3), (19,18), (22,3), (23,13), (24,13), (28,13), (29,0)}
Final Strips = {(1,11), (3,13), (9,0), (12,7), (16,3), (19,18), (22,3), (23,13), (29,0)}
The overall complexity is O(nlgn). This algorithm works for any arbitrary ordered dataset. Note that there are certain edge cases. For example, in case of buildings starting at same left we want to take the taller one. So, we sort the left coordinates by breaking tie using taller height between two buildings.
public static class Building{
int l;
int h;
int r;
public Building(int left, int height, int right){
l = left;
h = height;
r = right;
}
}
public static ArrayList<int[]> skyLine(Building[] buildings){
int n = buildings.length;
Building[] start = Arrays.copyOf(buildings, n);
Building[] end = Arrays.copyOf(buildings, n);
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(n, Collections.reverseOrder());
ArrayList<int[]> strips = new ArrayList<int[]>();
//sort based on left coordinate of a building i.e. start of a range
Arrays.sort(start, new Comparator<Building>() {
@Override
public int compare(Building o1, Building o2) {
int c = Integer.compare(o1.l, o2.l);
if(c == 0){
c = Integer.compare(o2.h, o1.h);
}
return c;
}
});
//sort based on right coordinate of a building i.e. end of a range
Arrays.sort(end, new Comparator<Building>() {
@Override
public int compare(Building o1, Building o2) {
return Integer.compare(o1.r, o2.r);
}
});
int i = 0, j = 0;
while(i < n || j < n){
//a new overlapping range i.e. a building
if(i < n && start[i].l <= end[j].r){
//update max height seen so far in current overlap
maxHeap.add(start[i].h);
//max height in current overlap including the current building
int maxHeightIncldingMe = maxHeap.isEmpty() ? 0 : maxHeap.peek();
//add th current strip with the left of building and max height seen so far in currne overlap
strips.add(new int[]{start[i].l, maxHeightIncldingMe});
//try next building
i++;
}
else{
//it's an end of a range of current overlap. So, we need to remove the height
//of this range i.e. building from the max heap
maxHeap.remove(end[j].h);
//max height of remaining buildings in current overlap
int maxHeightExcldingMe = maxHeap.isEmpty() ? 0 : maxHeap.peek();
//add the current strip with the right of building and max height of remaining buildings
strips.add(new int[]{end[j].r, maxHeightExcldingMe});
//update end index
j++;
}
}
//strips.add(new int[]{end[n-1].r, 0});
//merge strips to remove successive strips with same height
ArrayList<int[]> mergedStrips = new ArrayList<int[]>();
int prevHeight = 0;
for(int[] st : strips){
if(st[0] == end[n-1].r && st[1] != 0){
continue;
}
if(prevHeight == 0){
prevHeight = st[1];
mergedStrips.add(st);
}
else if(prevHeight != st[1]){
prevHeight = st[1];
mergedStrips.add(st);
}
}
return mergedStrips;
}