C++ O(N*logN) solution using a multiset


  • 0
        vector<pair<int, int>> getSkyline(vector<vector<int>>& blg) {
            
            vector<vector<int>> points;       
            for (auto& b : blg) { // O(N)
                points.push_back({ b[0], -b[2] }); // start point
                points.push_back({ b[1],  b[2] }); // end point
            }
            sort(points.begin(), points.end(), // O(N*logN)
                 [](vector<int>& a, vector<int>& b)
                 { return a[0] != b[0]? a[0] < b[0] : a[1] < b[1]; });
            
            vector<pair<int, int>> res;
            multiset<int> s = {0}; int prevMax = 0;
            for (auto& p : points) { // O(N)          
                (p[1] < 0)? s.insert(-p[1]) : s.erase(s.find(p[1])); // O(logN)
                int curMax = *s.rbegin();
                if (curMax != prevMax) 
                    res.emplace_back(p[0], curMax), prevMax = curMax;   
            }
                
            return res; 
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.