Skyline Problem in C++
We have given n rectangular buildings in a 2-dimensional city. Here, to compute the Skyline of the given n rectangle structures in a two-dimensional metropolis while removing hidden lines, the primary job is to delete all portions of systems that are not visible after viewing them from a distance.
A triplet represents each building, and all structures have a standard bottom (left, ht, right)
- Left: Is the left side of x coordinated(or wall)?
- Right: The right side's x coordinate.
- Ht: The building's height is indicated by ht.
An urban skyline is made up of many rectangular strips. A pair (left, ht) is used to describe a rectangular strip, where left denotes the x coordinate of the strip's left side and its height.
Example:
Buildings[][] = 1, 11, 5, 2, 6, 7, 9, 12, 14, 3, 25, 19, 18, 22, 23, 13, 29, 24, and 4 (in that order)
Output: 1, 11, 3, 13, 9, 0; 12, 7; 16, 3; 19, 18; 22, 3; 23, 13; 29, 0;
Approach:
- Retrieve the left wall location, height, and correct wall location values for each structure from the triplets provided.
- Keep the pair of the right wall's total height, and the left wall's negative height value in a vector called walls. This is done to distinguish between the left and right borders of the same building.
- Order the walls from highest to lowest.
- Cross the vector walls, and if a left wall is discovered, put its height in the multiset M. If a suitable barrier is met in any other case, take the multiset's appropriate height out.
- Verify whether the top value has changed. Update the maximum value and save the current wall's abscissa if it has changed (x-coordinate).
- The value pairs kept in the skyline vector should be printed.
Example:
// C++ programme for themethod described above
#include <bits/stdc++.h>
usingnamespace std;
// work to construct a skyline
vector<pair<int, int>>
create skylines(vector<vector<int>>& buildings)
{
// learn how manybuildings there are.
int N = buildings.size();
// To keep track of the buildings' left and right wall positions.
vector<pair<int, int>> wall;
// triplet of architectural elements and parameters
int left, height, right;
for (inti = 0; i< N; i++) {
// veer to the left of the building
left = buildings[i][0];
// veer to the left of the building
height = buildings[i][1];
// the appropriate building location
right = buildings[i][2];
// Keep left point and height in mind.
// from the left wall.
// Negative value indicates the left wall.
// first be added into the multiset
// identical abscissa(x) as the right wall
wall.push_back({ left, -height });
// Store the right wall's correct point and height.
wall.push_back(
make_pair(right, height));
}
// order the walls from highest to lowest
sort(wall.begin(), wall.end());
// output storing Skyline
vector<pair<int, int>> skyline;
// Begin a multiset with
// Organize the heights of the left wall.
multiset<int>leftWallHeight = { 0 };
// Maximum height currently among leftWallHeights
int top = 0;
// Through the sorted walls, turn.
For (autow wall) {
// if one finds the left wall
if (w.second< 0) {
// Add the height.
left all eight.insert(-w.second);
}
// if one finds the right wall
else {
// Take the height down
left all eight.erase(
left all eight.find(w.second));
}
//.rbegin(): Mark a skyline point if the top changes. backward iteration
if (*leftWallHeight.rbegin() != top) {
top = *leftWallHeight.rbegin();
skyline.push_back(
make_pair(w.first, top));
}
}
//Skyline to print again Skyline
return Skyline;
}
// Print the output skyline using this function.
voidprint skyline(
vector<vector<int>>& buildings)
{
// Skyline creation function call
vector<pair<int, int>> skyline
= create skylines(buildings);
cout<< "Skyline for the given."
<< " buildings:\n{";
for (autoit: skyline) {
cout<< "{" <<it.first<< ", "
<<it.second<< "} ";
}
cout<< "}";
}
//Driver Number
int main()
{
vector<vector<int>> buildings;
//Given the wall's height and the left and right locations,
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 } };
//Feature Call
print skyline(buildings);
return 0;
}
Output:

Time Complexity: O(n*log(N))
Auxiliary Space: O(N)