218

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> heights;
        for(auto b: buildings){
            heights.push_back({b[0], -b[2]});
            heights.push_back({b[1], b[2]});
        }
        sort(heights.begin(), heights.end());

        multiset<int> pq;
        pq.insert(0);
        int curMax = 0;
        vector<vector<int>> ans;
        for(auto height: heights){
            int h = height.second;
            if(h<0)
                pq.insert(-h);
            else
                pq.erase(pq.find(h));
            if(curMax != *pq.rbegin()){
                curMax = *pq.rbegin();
                ans.push_back({height.first, curMax});
            }
        }
        return ans;
    }
};