218. The Skyline Problem

sweep line O(nlogn)
使用map记录事件，然后遍历map进行事件处理
用一个multiset来从高到低维护所有楼高度的『开始』和『结束』，遇到开始则加入，遇到结束则删除（只删除一个instance），每次遇到『新高』（有可能是开始，也有可能是结束，每次都要先调整multiset之后再从multiset开头取出来『新高』），然后和之前记录的高度对比，如果一样则忽略，否则要记录下来并更新记录

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        map<int, vector<pair<int, bool>>> m; // 用map记录所有『事件』用一个bool来表示楼的左边还是右边（开始还是结束）
        for (const auto &b : buildings) {
            m[b[0]].emplace_back(b[2], true);
            m[b[1]].emplace_back(b[2], false);
        }
        multiset<int, greater<int>> s; // set不支持duplicate，priority_queue不支持删除任一元素，所以只能用multiset，从高到低记录每个高度的楼的左边和右边
        int pre = 0;
        vector<pair<int, int>> res;
        for (const auto &p : m) {
            for (const auto &pp : p.second) { // 遍历每个位置的所有可能高度（『事件』），『开始』则向multiset里添加新高度，否则从中删除一个copy
                if (pp.second) { // 遇到『新高』则加入multiset
                    s.emplace(pp.first);
                }
                else {
                    s.erase(s.find(pp.first)); // 遇到某个楼的右边『结束』则从multiset删除指定iterator，不会影响其他相同元素
                }
            }
            int h = s.empty() ? 0 : *s.begin();
            if (h != pre) { // 如果当前位置有『新高』，则跟之前的高度对比并记录下来
                res.emplace_back(p.first, h);
                pre = h;
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        map<int, vector<pair<int, bool>>> m;
        for (const auto &b : buildings) {
            m[b[0]].emplace_back(b[2], true);
            m[b[1]].emplace_back(b[2], false);
        }
        vector<vector<int>> res;
        multiset<int, greater<int>> s;
        int prev = -1;
        for (const auto &[k, v] : m) {
            for (auto [h, isL] : v) {
                if (isL) {
                    s.insert(h);
                } else {
                    s.erase(s.find(h));
                }
            }
            int mx = s.empty() ? 0 : *begin(s);
            if (mx != prev) {
                res.push_back({k, mx});
                prev = mx;
            }
        }
        return res;
    }
};