# A classic Sweep line solution with detailed comments

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

//
// While this looks redundant it comes in handy for
// comparing between different points with same coordinates
//
struct Line
{
int Height;

Line(int H)
:
Height(H)
{}

};

struct Point
{
int Loc;
bool Left;
Line *Ln;

Point(int Lc, bool Lft, Line *L)
:
Loc(Lc),
Left(Lft),
Ln(L)
{}

};

//
// Sorting is done based first by x coordinat, then by left or right point (left first),
// then for two points with same x and both are left we chose based on higher,
// if two points with same x and both right we chose the shorter
//
friend bool operator<(const Point& p1, const Point &p2)
{
return (p1.Loc < p2.Loc || (p1.Loc == p2.Loc && p1.Left == true && p2.Left != true) ||
(p1.Loc == p2.Loc && p1.Left == true && p2.Left == true && p1.Ln->Height > p2.Ln->Height) ||
(p1.Loc == p2.Loc && p1.Left == false && p2.Left == false && p1.Ln->Height < p2.Ln->Height));
}

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings)
{
vector<pair<int, int> > Res;
vector<Point> Points;
map<int,Line*> S;
int CurrMaxHeight = INT_MIN;

for (auto &B : buildings)
{
Line *L = new Line(B[2]);
Point Left(B[0],true,L), Right(B[1],false,L);
Points.push_back(Left);
Points.push_back(Right);
}

//
// Sort the buildings based on the operator< above
//
sort(Points.begin(),Points.end());

for (auto &P : Points)
{
int Height = (P.Ln)->Height;

if (P.Left)
{
//
// if the Height of the current point being inserted
// is higher than the Max so far,
// update the max so far first, insert this new pair into
// the result vector
//

if(Height > CurrMaxHeight)
{
CurrMaxHeight = Height;
Res.push_back(make_pair(P.Loc,CurrMaxHeight));
}

//
// Just insert the <Height,Line> into the map
// Notice that there could be another pair <Height,Line2> already in the map
// in this case we'll override that pair with the new one.
// Since we already sorted based on height, this has no implications on the result
// but will serve as when we need to delete the line
//

S[Height] = P.Ln;
}
else
{
auto Iter = S.find(Height);

if(Height == CurrMaxHeight)
{
//
// if the current point's line
// does not correspond to the line in the map
// (which has the same height) we just ignore it.
// otherwise we enter the if below
//
if(P.Ln == Iter->second)
{
//
// first erase this <height,Line*> pair
//
S.erase(Iter);

//
// if this was the last pair then CurrMaxHeigth becomes 0
//

if(S.empty())
{
CurrMaxHeight = 0;;
}
else
{
//
// We get the Heighest height in the map
// and update our CurrMaxHeight
//
auto Prev = prev(S.end());
CurrMaxHeight = Prev->first;
}

Res.push_back(make_pair(P.Loc,CurrMaxHeight));
}
}
else
{
//
// we are trying to delete
// a <Height,Line*> that is lower in height than the max so far
// so who cares!
//

if(P.Ln == Iter->second)
{
S.erase(Iter);
}
}
}
}

return (Res);
}
};
``````

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