The basic idea is:

1.put the start and end of each rectangle into a multimap, we will scan it later. The second parameter of the pair is its height.(i.e. as for [0,5,3] we will put {0, 3} and {5, -3} into the map)

2.for each element in multimap, if the height is greater than zero, we put it into multiset, else we find and erase it from the set.

- the multiset means at each x value, the existing rectangle.
- After processing each x value, the max in the set is what we need, just put it into the vector.

```
class Solution {
public:
struct comp{
bool operator ()(const int &a, const int &b){ return a > b;}
};
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int> > ret;
multimap<int, int> mii;
for (int i = 0; i < buildings.size(); ++i){
vector<int> &vi = buildings[i];
mii.insert(make_pair(vi[0], vi[2]));
mii.insert(make_pair(vi[1], vi[2] * -1));
}
multiset<int, comp> msi;
msi.insert(0);
while (mii.size()){
int last_height = *msi.begin();
int cur = mii.begin()->first;
while (mii.begin()->first == cur){
int height = mii.begin()->second;
if (height > 0){
msi.insert(height);
}else{
msi.erase(msi.find(height * -1));
}
mii.erase(mii.begin());
}
if (*msi.begin() != last_height){
ret.push_back(make_pair(cur, *msi.begin()));
}
}
return ret;
}
};
```