Solution.cpp

// 区间离散化解法（低效 120ms）
class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        set<int> poss ;
        map<int, int> m ;
        for (auto v: buildings)
        {
            poss.insert(v[0]) ;
            poss.insert(v[1]) ;
        }
        
        int i = 0 ;
        for (int pos: poss)
            m.insert(pair<int, int>(pos, i++)) ;
        
        vector<int> highs(m.size(), 0) ;
        for (auto v: buildings)
        {
            const int b = m[v[0]], e = m[v[1]] ;
            for (int i = b; i < e; ++i)
                highs[i] = max(highs[i], v[2]) ;
        }
        
        vector<pair<int, int>> res ;
        vector<int> mm(poss.begin(), poss.end()) ;
        for (int i = 0; i < highs.size(); ++i)
        {
            if (highs[i] != highs[i+1])
                res.push_back(pair<int, int>(mm[i], highs[i])) ;
            else
            {
                const int start = i ;
                res.push_back(pair<int, int>(mm[start], highs[i])) ;
                while (highs[i] == highs[i+1])
                    ++i ;
            }
        }
        return res ;
    }
};