// https://leetcode.com/problems/the-skyline-problem/discuss/61222/17-Line-O(n-log-n)-time-O(n)-space-C%2B%2B-Accepted-Easy-Solution-w-Explanations

// Idea - first we see max height among current, then when that max height gets over then we go to next max height, and so on....
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> heights;
        for(auto &building: buildings) {
            heights.push_back({building[0], -building[2]});
            heights.push_back({building[1], building[2]});
        }
        sort(heights.begin(), heights.end());
        multiset<int> currentHeights;
        currentHeights.insert(0);
        vector<vector<int>> skyline;
        for(auto &[x, y]: heights) {
            if(y < 0) {
                currentHeights.insert(-y);
            }
            else {
                currentHeights.erase(currentHeights.find(y));
            }
            if(skyline.empty() || skyline.back()[1] != *currentHeights.rbegin()) {
                skyline.push_back({x, *currentHeights.rbegin()});
            }
        }
        return skyline;
    }
};