# 26 ms C++ submission. Scan-lines with three stages

• ``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
if (buildings.size() == 0) {
return vector<pair<int, int>>();
}
// Stage 1: produce scan lines
vector<pair<int, int>> lines;   lines.reserve(buildings.size() * 2);
for (int i = 0; i < buildings.size(); ++i) {
lines.push_back(make_pair(buildings[i][0], i));
lines.push_back(make_pair(buildings[i][1], i));
}
sort(lines.begin(), lines.end());

// Stage 2: Get the y for each scan line.
// There might be some many x with same y in the array
vector<pair<int, int>> sl;
priority_queue<pair<int, int>> heights;
for (int i = 0; i < lines.size(); ) {
int x = lines[i].first;
for (; i < lines.size() && (i == 0 || lines[i].first == x); ++i) {
heights.push(make_pair(buildings[lines[i].second][2], lines[i].second));
}
while (!heights.empty() && buildings[heights.top().second][1] <= x) {
heights.pop();
}
sl.push_back(make_pair(x, !heights.empty() ? heights.top().first : 0));
}

// Stage 3: remove the items that has same y as previous item
int inserti = 0;
for (int i = 1; i < sl.size(); ++i) {
if (sl[i].second != sl[inserti].second) {
sl[++inserti] = sl[i];
}
}
sl.resize(inserti + 1);
return sl;
}
};
``````

This is not the fastest one, but I think the algorithm is easy to understand.

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