share a c++ solution using heap and sweeping idea


  • 0
    Z

    The idea is to

    1. Construct the positions where skyline may need to be updated,
      This is whenever a building start or end, such vector is denoted by "vector<pair<int,int>> events" where pair.first is the
      location, pair.second is the id of the building, 0~n-1 for start (left of building), -1 ~ -n for end (right of building)

    2. At each location where updated needs to be checked, first add new buildings(if any) into max_heap(by its height)
      when make sure finishing all events at this location, condition is ( i = n_event - 1 || x[i] < x[i+1]), get the top element
      from the heap, which corresponds to the highest building.

    3. Notice this building maybe invalid ( if x > buildings.right), so pop top element until finds a valid one, and its height will
      be the h at the location, add to solution if h is different from previous.

    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int,int>> events;   // first: x, second: id, >=0 for st, <0 for nd
            for(int i = 0; i < buildings.size(); i++) {
                events.push_back({buildings[i][0],i});
                events.push_back({buildings[i][1],-i-1});
            }
            sort(events.begin(), events.end());       
            priority_queue<vector<int>, vector<vector<int>>, pq_comp> pq;
            vector<pair<int,int>> res;
            for(int i = 0; i < events.size(); i++) {
                int id = events[i].second, x = events[i].first;
                if(id >= 0) {
                    pq.push(buildings[id]);                
                }
                if(i == events.size() - 1 || x < events[i+1].first) {
                    while(!pq.empty() && pq.top()[1] <= events[i].first ) {
                        pq.pop();
                    }
                    int h = (pq.empty())?(0):(pq.top()[2]);
                    if(res.empty() || h != res.back().second) {
                        res.push_back({x, h});
                    }
                }
            }
            return res;
        }
    private:
        struct pq_comp {
            bool operator() (const vector<int> &x, const vector<int> &y) {
                return x[2] < y[2];
            }
        };
    };
    

Log in to reply
 

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