# C++, very fast(22ms), kind of complicated(140 lines)

• ``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int> > res; // result
if (buildings.size() == 0)
return res;

list<pair<int, pair<int, int> > > h_x1_x2;
for (int i = 0; i < buildings.size(); i ++)
h_x1_x2.push_back(make_pair(buildings[i][2], make_pair(buildings[i][0], buildings[i][1]))); //

h_x1_x2.sort(my_sort); // Sort

vector<pair<int, int> > x1_x2; // store blocks' coordinate
list<pair<int, pair<int, int> > >::iterator it = h_x1_x2.begin();
while (it != h_x1_x2.end()) {
const int x1 = (*it).second.first;
const int x2 = (*it).second.second;
if (x1_x2.size() == 0)
res.push_back(make_pair(x1, (*it).first));
//=========Update Result=======
for (int i = 0; i < x1_x2.size(); i ++) {
if (x1 < x1_x2[i].first && x2 > x1_x2[i].second) { // conclude several blocks
res.push_back(make_pair(x1, (*it).first));
res.push_back(make_pair(x1_x2[i].second, (*it).first));
i ++;
while (i < x1_x2.size()) {
if (x1_x2[i].second < x2)
res.push_back(make_pair(x1_x2[i].second, (*it).first));
i ++;
}
break;
}
if (x1 >= x1_x2[i].first && x2 <= x1_x2[i].second) // be concluded
break;
if (x1 < x1_x2[i].first && x2 <= x1_x2[i].second) { // overlap on left
res.push_back(make_pair(x1, (*it).first));
break;
}
if (x1 <= x1_x2[i].second && x2 > x1_x2[i].second) { // overlap on right
res.push_back(make_pair(x1_x2[i].second, (*it).first));
i ++;
while (i < x1_x2.size()) {
if (x1_x2[i].second < x2)
res.push_back(make_pair(x1_x2[i].second, (*it).first));
i ++;
}
break;
} else if (i == x1_x2.size() - 1) { // non-overlap
res.push_back(make_pair(x1, (*it).first));
}
}
//========end==========

Add(x1, x2, x1_x2); // Update blocks
it ++;
}
for (int i = 0; i < x1_x2.size(); i ++)
res.push_back(make_pair(x1_x2[i].second, 0)); // Add the ground

resSort(res, 0, res.size() - 1); // Quick Sort
resSort_1(res); // Sort dots with same corrdiante
resDel(res); // Delete dots on the same line
return res;
}

private:
void resSort_1(vector<pair<int, int> >& res) {
for (int i = 0; i < res.size() - 1; i ++) {
if (res[i].first == res[i + 1].first && res[i].second > res[i + 1].second) {
int x = res[i].second;
res[i].second = res[i + 1].second;
res[i + 1].second = x;
}
}
}

void resDel(vector<pair<int, int> >& res) {
for (int i = 0; i < res.size() - 1; i ++) {
if (res[i].second == res[i + 1].second) { // same height
res.erase(res.begin() + i + 1);
i --;
}
if (res[i].first == res[i + 1].first) { // same coordinate
if (res[i].second < res[i + 1].second)
res.erase(res.begin() + i  + 1);
else
res.erase(res.begin() + i);
i --;
}
}
}

void resSort(vector<pair<int, int> >& res, int start, int end) {
if (start >= end)
return;
int first = start;
int last = end;

pair<int, int> key = res[first];
while (first < last) {
while (first < last && res[last].first >= key.first)
last --;
res[first] = res[last];
while (first < last && res[first].first <= key.first)
first ++;
res[last] = res[first];
}
res[first] = key;
resSort(res, start, first - 1);
resSort(res, first + 1, end);
}

void Add(const int x1, const int x2, vector<pair<int, int> >& x1_x2) {
if (x1_x2.size() == 0)
x1_x2.push_back(make_pair(x1, x2));
for (int i = 0; i < x1_x2.size(); i ++) {
if (x2 < x1_x2[i].first) { // all block non-overlap, to the left
x1_x2.insert(x1_x2.begin() + i, make_pair(x1, x2));
return;
} else if (x1 < x1_x2[i].first && x2 >= x1_x2[i].first && x2 <= x1_x2[i].second) { // overlap on left part
x1_x2[i].first = x1;
return;
} else if (x1 >= x1_x2[i].first && x2<= x1_x2[i].second) { // be concluded by the i'th block
return;
} else if (x1 <= x1_x2[i].second && x2 > x1_x2[i].second) { // concluded the i'th block，or overlap on right part
int new_x1 = min(x1, x1_x2[i].first);
x1_x2.erase(x1_x2.begin() + i);
return;
} else if (i == x1_x2.size() - 1){ // all block non-overlap, to the right
x1_x2.push_back(make_pair(x1, x2));
}
// continue;
}
}

static bool my_sort(pair<int, pair<int, int> >& l1, pair<int, pair<int, int> >& l2) {
return (l1.first > l2.first);
}
};
``````

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