The skyline problem in C++
Educative Answers TeamIn the skyline problem, the user is provided with the coordinates of rectangular buildings that have varying widths and heights. The user is required to return a silhouette that traces the outlines of all the buildings.
Note: A city’s skyline is made up from the outer contour of the city’s silhouette. This silhouette can be seen when a city is viewed from a distance.
Sweeping line algorithm
The simplest solution to this problem would be to use the sweeping line algorithm. However, before continuing, there are a few underlying assumptions that we need to state.
- The right coordinate of a building will always be greater than the left coordinate.
- The difference between the value of the right coordinate and the left coordinate, of any building, will always be greater than 0.
- Critical points are those points where a building starts or ends.
The basic idea of the sweeping line algorithm is to move a vertical line from the left end towards the right end. At any point, the height of the silhouette will be the maximum height of the building that the sweeping line is intersecting.
Steps involved
- Sort the array of buildings in order.
- Find the critical points among all the buildings.
- Run a loop from the smallest critical point to the largest.
- Add all the buildings, whose starting point is smaller than the critical value and whose ending point is larger than the critical value, to a set.
Examples
1. The c++ code will look like this:
for (int point = 0; point < numCriticalPoints; ++points){
for (int current = 0; current < numBuildings; ++current){
if (((buildings[current].start)< CriticalPoint[point])
&& ((buildings[current].end)> CriticalPoint[point])){
set_of_buildings.insert(buildings[current])
}
}- The height of the silhouette should be the height of the tallest building in the set. If the set is empty, the height will be zero.
2. The c++ code would look like this:
if (set_of_buildings.size() == 0) {
height_of_silhouette = 0
}
else {
height_of_silhouette = findMax(set_of_buildings)
}- After the loop breaks, we will have the values of all the heights, of all the silhouettes, at every critical point. The height between any two critical points will be equal to the height of the first critical point.
RELATED TAGS
View all Courses
