# Scan solution in c++(850ms)

• ``````the basic idea : scan from left to right, check the most left edge.
``````

if the edage is the left of some rectangle, if the rectangle is the topmost, we will probably add a new line segment to the result and add it to a set(when we reach the right edge, we will remove it).

if the edge is the right, we will remove it from the set and add(update) the result.

``````struct cmp
{
cmp(vector<vector<int>>* p, bool t)
{
p_ = p;
t_ = t;
}
bool operator ()(const int i, const int j) const
{
if(t_)
{
const vector<int>& v1 = p_->at(i);
const vector<int>& v2 = p_->at(j);
if(v1[2] != v2[2]) return v1[2] < v2[2];

return v1[1] < v2[1];
}
return p_->at(i)[1] > p_->at(j)[1];
}
vector<vector<int> >*	p_;
bool					t_;
};
vector<pair<int, int>> getSkyline(vector<vector<int>>& b)
{
typedef pair<int, int> point;
vector<point> res;

if(b.empty()) return res;

int size = (int)b.size();
point pt;

cmp ch(&b, true);
cmp cr(&b, false);

priority_queue<int, vector<int>, cmp> qh(ch), qr(cr);

int i = 0;
// from left to right, scan the most left house.
while(i < size || !qr.empty())
{
//choose one from the heap
if(i == size || (!qr.empty() && b[qr.top()][1] < b[i][0]))
{
int idx = qr.top();
qr.pop();

while(!qh.empty() && b[qh.top()][0] == -1)
qh.pop();

if(idx == qh.top()) //highest one
{
qh.pop();
while(!qh.empty() && b[qh.top()][0] == -1)
qh.pop();

// got the second highest one, if not, height is 0
point pt = !qh.empty() ? point(b[idx][1], b[qh.top()][2]) : point(b[idx][1], 0);

if(!res.empty() && res.back().first == pt.first && res.back().second > pt.second)
res.back().second = pt.second;
else
res.push_back(pt);
}
else
{
b[idx][0] = -1;// marked as deleted.(also, the qh,qr can be replaced with set)
}
}
else // new rectangle
{
if(i > 0 && b[i - 1] == b[i])
{
++i;
continue;
}
qh.push(i);
qr.push(i);
if(qh.top() == i)// highest one
{
if(!res.empty() && res.back().second == b[i][2])
;
else if(!res.empty() && res.back().first == b[i][0])
res.back().second = b[i][2];
else
res.push_back(point(b[i][0], b[i][2]));
}
++i;
}
}
return res;
}``````

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