@zhiqing_xiao so for coords, you don't really need a multimap, just a single vector will do - algorithrm based on @maplain and @jinwu's solutions here and here. But their java solutions erases elements in a priority_queue, which costs O(n) each time, and making their solution O(n^2).

In C++, we can use multiset's find function combined with erase(), costing only O(log(n)), making our solution O(nlog(n)).

I'm posting the algorithm under this thread to make it easier to see for all the C++ coders out there (only 16 lines!).

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