C++ worst case O(n log(n)) solution using a priority queue


  • 0
    G

    The idea is that we use a priority queue to store all of the buildings we pass. From it, we get the desired building by popping it until getting a building at the current position, which contributes a point to the result if its height is different than the last point. We then either move to the next building in the list, adding it to the priority queue, or to the end of the current building, which ever is closer. When the queue is empty, we add a point at height 0 at the end of the last building since there are no buildings after this position and add the next building from the list to the queue and continue.

    class Solution {
    public:
        struct Tallest {
            bool operator()(const vector<int> *b1, const vector<int> *b2) const noexcept {
                return b1->at(2) < b2->at(2);
            }
        };
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            priority_queue<vector<int>*, vector<vector<int>*>, Tallest> q;
            vector<pair<int,int>> result;
            for(auto input = buildings.begin(), end = buildings.end(); input < end;){
                int x = input->at(0);
                q.push(&(*input)); // q is empty, add next building
                ++input;
                while(input != end && input->at(0) == x) { // add all buildings at next x
                    q.push(&(*input));
                    ++input;
                }
                while(q.size()){
                    vector<int>& building = *q.top(); // get tallest building at x
                    if(building[1] <= x) { // passed the building, go to next one
                        q.pop();
                        continue;
                    }
                    if(result.empty() || result.back().second != building[2]){ // don't add coordinate if it has same height as previous
                        result.emplace_back(x, building[2]);
                    }
                    if(input != end){
                        if(input->at(0) <= building[1]){ // add next building
                            x = input->at(0);
                            q.push(&(*input));
                            ++input;
                            while(input != end && input->at(0) == x) { // add all buildings at next x
                                q.push(&(*input));
                                ++input;
                            }
                            continue;
                        }
                    }
                    q.pop();
                    x = building[1]; // no new buildings start before tallest building ends, next point of interest is where this building ends
                }
                result.emplace_back(x, 0);
            }
            return result;
        }
    };
    

Log in to reply
 

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