# [recommend for beginners]clean C++ implementation with detailed explanation

• ``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> edges;
int left, right, height;
for(int i=0; i<buildings.size(); i++){
left=buildings[i][0];
right=buildings[i][1];
height=buildings[i][2];
/*** make sure : for the same left point we use the bigger height ***/
edges.push_back(make_pair(left, -height));
edges.push_back(make_pair(right, height));
}
sort(edges.begin(), edges.end());
vector<pair<int, int>> result;
/*** use the multiset to store the max height util current pos ***/
multiset<int> m;
/*** left most height ***/
m.insert(0);
int pre=0, cur=0;
for(int i=0; i<edges.size(); i++){
pair<int, int> e=edges[i];
if(e.second < 0)  m.insert(-e.second);
else m.erase(m.find(e.second));
cur=*(m.rbegin());
if(cur!=pre){
result.push_back(make_pair(e.first, cur));
pre=cur;
}
}
return result;
}
};``````

• ``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> result;
vector<pair<int, int>> edges;

for(auto it : buildings) {
int left = it[0];
int right = it[1];
int height = it[2];
edges.push_back(make_pair(left, -height));
edges.push_back(make_pair(right, height));
}

sort(edges.begin(), edges.end());

multiset<int> m;
int pre = 0, cur = 0;

m.insert(0);
for(auto it : edges) {
int pos = it.first;
int height = it.second;
if(height < 0) {
m.insert(-height);
}
else {
m.erase(m.find(height));
}
cur = *(m.rbegin());
if(cur != pre) {
result.push_back(make_pair(pos, cur));
pre = cur;
}
}

return result;
}
};``````

• Here is the LintCode provided related Building Outline problem

As the output format is changed , so I just change the above code to get the AC implementation ....

Here is the CODE :

``````bool compare(pair<int, int> a, pair<int, int> b) {
return a.first == b.first ?  a.second < b.second : a.first < b.first;
}
class Solution {
public:
/**
* @param buildings: A list of lists of integers
* @return: Find the outline of those buildings
*/
vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
vector<vector<int>> result;
vector<pair<int, int>> dict;
int size_ = buildings.size();
if(size_ == 0)  return result;

for(int i = 0; i < size_; i++) {
dict.push_back(make_pair(buildings[i][0], -buildings[i][2]));
dict.push_back(make_pair(buildings[i][1], buildings[i][2]));
}
sort(dict.begin(), dict.end(), compare);

multiset<int> max_height {0};
int pre = 0;
for(int i = 0; i < dict.size(); i++) {
//cout<<i<<":"<<dict[i].first<<dict[i].second<<endl;
if(dict[i].second < 0) {
max_height.insert(-dict[i].second);
} else {
max_height.erase(max_height.find(dict[i].second));
}

int cur = *(max_height.rbegin());
if(cur != pre) {
result.push_back({dict[i].first, 0, cur});
pre = cur;
}
}

//cout<<result.size()<<endl;
for(int i = 0; i < result.size() - 1; i++) {
result[i][1] = result[i+1][0];
}

vector<vector<int>> outline;
for(int i = 0; i < result.size(); i++) {
if(result[i][2] != 0)  outline.push_back(result[i]);
}
return outline;
}
};``````

• Using multiset is a great idea! Much easier to understand than using a heap.

• You are right !

• the key idea is how to sort the array by position and height, and then just keep it by processing a heap

• This post is deleted!

• ``````
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int> > h, res;
multiset<int> m;
int pre = 0, cur = 0;
for (auto &a : buildings) {
h.push_back({a[0], -a[2]});
h.push_back({a[1], a[2]});
}
sort(h.begin(), h.end());
m.insert(0);
for (auto &a : h) {
if (a.second < 0) m.insert(-a.second);
else m.erase(m.find(a.second));
cur = *m.rbegin();
if (cur != pre) {
res.push_back({a.first, cur});
pre = cur;
}
}
return res;
}
};
``````

• This post is deleted!

• Nice solution. My first thinking was about to write a hash heap and soon got headache for that. Using multiset make things much easier!

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