C++ O(NlogN) solution with map


  • 0
    H

    The idea is using a map<int, int, greater<int>> m to maintain the height and right position. For each new building, before insert the <height, right> to the map, check current the highest buildings right position, if it result skyline change, add it to result.

    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            map<int, int, greater<int>> m;
            vector<pair<int, int>> res;
            for (auto b : buildings) {
                int l = b[0], r = b[1], h = b[2];
                helper(res, m, l);
                m[h] = max(m[h], r);
                if (res.empty() || m.begin()->first > res.back().second) {
                    if (!res.empty() && l == res.back().first) {
                        res.back().second = m.begin()->first;
                    }
                    else {
                        res.emplace_back(l, m.begin()->first);
                    }
                }
            }
            helper(res, m, 0);
            return res;
        }
        
        void helper(vector<pair<int, int>>& r, map<int, int, greater<int>>& m, int limit) {
            int x = 0;
            while (!m.empty() && (!limit || m.begin()->second < limit)) {
                x = max(x, m.begin()->second);
                m.erase(m.begin());
                // Only put to result the current right pos is larger than the previous one
                if (m.empty() || m.begin()->second > x) {
                    r.emplace_back(x, m.empty() ? 0 : m.begin()->first);
                }
            }
        }
    };
    

Log in to reply
 

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