The Skyline Problem.cpp

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<tuple<int, int, int>> criticalPoints;
        for(auto&& building : buildings)
        {
            criticalPoints.push_back(make_tuple(building[0], building[2], building[1]));
            criticalPoints.push_back(make_tuple(building[1], -1, -1));
        }
        auto comp = [](const tuple<int, int, int>& lhs, const tuple<int, int, int>& rhs){return get<0>(lhs) == get<0>(rhs)? get<1>(lhs) > get<1>(rhs): get<0>(lhs) < get<0>(rhs);};
        sort(criticalPoints.begin(), criticalPoints.end(), comp);
        priority_queue<pair<int, int>> heights;
        vector<pair<int, int>> res;
        for(auto&& point : criticalPoints)
        {
            while(heights.size() && heights.top().second <= get<0>(point))heights.pop();
            if(get<2>(point) >= 0)heights.push({get<1>(point), get<2>(point)});
            int currHeight = heights.empty()? 0: heights.top().first;
            if(res.empty() || currHeight != res.back().second)res.push_back({get<0>(point), currHeight});
        }
        return res;
    }
};