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) {

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)