# C++ line sweep algorithm with very detailed explanation - very good for beginners.

• ``````class Solution {
public:

struct Point{
int x;
int h;
bool start;

Point(int c, int height,bool isStart):
x(c),h(height),start(isStart){}
};

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
multiset<int> tree;
vector<Point> v;
vector<pair<int,int> > result;
int maxSoFar = 0;
tree.insert(0);

for(auto &b : buildings){
//create two end points one for start and one for end
Point p1 = {b[0],b[2],true};
Point p2 = {b[1],b[2],false};
v.push_back(p1);
v.push_back(p2);
}

//sort the endpoints while addressing edge cases:
//1. if the x coordinates are different choose the point with the lesser x coordinate
//2. otherwise,
//2.a if both point are start points choose the higher point
//2.b if both points are end points choose the lower point
//2.c if one is start and one is end - choose the start to come first

sort(v.begin(),v.end(),[](const Point &p1, const Point &p2)->bool{
if(p1.x < p2.x){
return true;
}
else if(p1.x == p2.x){
if(p1.start && p2.start){
return p1.h > p2.h;
}
else if(!p1.start && !p2.start){
return p1.h < p2.h;
}
else{
return p1.start;
}
}

return false;
});

//traverse the sorted points and insert/remove them from the multiset
for(auto &p : v){

//if this is a start point & its hieght is bigger than the hieghst point currently in our set
// add this point to the result (notice that in the begining the first height in the tree is 0).

if(p.start){
if(p.h > maxSoFar){
result.push_back({p.x,p.h});
}

tree.insert(p.h);
maxSoFar = max(maxSoFar,p.h);
}
else{

// since this is a multiset, we need to pick only one of hieghts corresponding to this point
auto per = tree.equal_range(p.h);

//erase that point
tree.erase(per.first);

if(maxSoFar == p.h){

//if that point was the hieghest look at the next hieghest point left in the set
int newMaxSoFar = *(prev(tree.end()));

// if they are different than add a new point to the result using the x coordinate of this point
// and the height of the remaining point in the set
// However, if they are similar, no need to add a the point to the queue as this new point is
// simply a continuation of the previous building.
if(newMaxSoFar != maxSoFar){
result.push_back({p.x,newMaxSoFar});
maxSoFar = newMaxSoFar;
}
}
}
}

return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.