# Line Sweeping Algorithm. Easier than I thought

• The code turns out to be simpler than I expect. Probably because we don't have to create our own BST class in this case. The set<> is enough.

``````struct EndPoint {
int x;
int h;
int i; // index into buildings array
EndPoint(int a, int b, int c)
{
x = a;
h = b;
i = c;
}
};

class comparison {
public:
bool operator()(const EndPoint & a, const EndPoint & b)
{
return a.x < b.x || (a.x == b.x && a.h < b.h);
}
};

class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int> > ret;
set<pair<int, int> > s; // first: height, second: x
vector<EndPoint> v;
for(int i=0;i<buildings.size();i++)
{
v.push_back(EndPoint(buildings[i][0], buildings[i][2], i));
v.push_back(EndPoint(buildings[i][1], buildings[i][2], i));
}

sort(v.begin(), v.end(), comparison());

int idx = 0;
while(idx < v.size())
{
int currX = v[idx].x;
int currH = 0;
while(v[idx].x == currX)
{
if(buildings[v[idx].i][0] == v[idx].x) // start point
{
s.emplace(v[idx].h, v[idx].x);
}
else // end point
{
s.erase(make_pair(v[idx].h, buildings[v[idx].i][0]));
}
idx++;
}

if(!s.empty())
{
auto it = --s.end();
currH = it->first;
}

if(ret.size() == 0 || currH != ret.back().second)
{
ret.push_back(make_pair(currX, currH));
}
}

return ret;
}
};
``````

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