My C++ code using one priority queue (812 ms)


  • 80
    D

    The idea is to do line sweep and just process the buildings only at the start and end points. The key is to use a priority queue to save all the buildings that are still "alive". The queue is sorted by its height and end time (the larger height first and if equal height, the one with a bigger end time first). For each iteration, we first find the current process time, which is either the next new building start time or the end time of the top entry of the live queue. If the new building start time is larger than the top one end time, then process the one in the queue first (pop them until it is empty or find the first one that ends after the new building); otherswise, if the new building starts before the top one ends, then process the new building (just put them in the queue). After processing, output it to the resulting vector if the height changes. Complexity is the worst case O(NlogN)

    Not sure why my algorithm is so slow considering others' Python solution can achieve 160ms, any commments?

    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int>> res;
            int cur=0, cur_X, cur_H =-1,  len = buildings.size();
            priority_queue< pair<int, int>> liveBlg; // first: height, second, end time
            while(cur<len || !liveBlg.empty())
            { // if either some new building is not processed or live building queue is not empty
                cur_X = liveBlg.empty()? buildings[cur][0]:liveBlg.top().second; // next timing point to process
    
                if(cur>=len || buildings[cur][0] > cur_X)
                { //first check if the current tallest building will end before the next timing point
                      // pop up the processed buildings, i.e. those  have height no larger than cur_H and end before the top one
                    while(!liveBlg.empty() && ( liveBlg.top().second <= cur_X) ) liveBlg.pop();
                }
                else
                { // if the next new building starts before the top one ends, process the new building in the vector
                    cur_X = buildings[cur][0];
                    while(cur<len && buildings[cur][0]== cur_X)  // go through all the new buildings that starts at the same point
                    {  // just push them in the queue
                        liveBlg.push(make_pair(buildings[cur][2], buildings[cur][1]));
                        cur++;
                    }
                }
                cur_H = liveBlg.empty()?0:liveBlg.top().first; // outut the top one
                if(res.empty() || (res.back().second != cur_H) ) res.push_back(make_pair(cur_X, cur_H));
            }
            return res;
        }
    };

  • 20

    Very nice idea, keeping smaller buildings alive under larger ones even though they ended already.

    You have a few unnecessary things, though. If I'm not mistaken, mycompare just does the default ordering, vector is the default container for priority_queue, the if(len>0) doesn't help, and you don't need a private section. I think removing that stuff would make your solution even better than it already is.

    About Python being faster: Yeah that's right, Python is faster now. Deal with it :-P. More seriously, here's the probable explanation.


  • 0
    D

    Thanks for your commments, especially the one about mycompare (I didn't know that). Updated as you suggested


  • 10

    I removed your comments (I wanted to see how it looks without them) and slightly changed the logic flow:

    struct Solution {
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int>> res;
            int cur=0, cur_X, cur_H, len = buildings.size();
            priority_queue<pair<int, int>> liveBlg;
            while(cur<len || !liveBlg.empty()) {
                if (liveBlg.empty() || cur<len && buildings[cur][0] <= liveBlg.top().second) {
                    cur_X = buildings[cur][0];
                    while(cur<len && buildings[cur][0] == cur_X) {
                        liveBlg.push(make_pair(buildings[cur][2], buildings[cur][1]));
                        cur++;
                    }
                } else {
                    cur_X = liveBlg.top().second;
                    while (liveBlg.size() && liveBlg.top().second <= cur_X)
                        liveBlg.pop();
                }
                cur_H = liveBlg.empty() ? 0 : liveBlg.top().first;
                if (res.empty() || (res.back().second != cur_H))
                    res.push_back(make_pair(cur_X, cur_H));
            }
            return res;
        }
    };
    

    I'm not saying it's better than yours, but personally I find it clearer to first check whether we're going to add or remove buildings, and to then assign cur_X only once. Also, since in case of a tie, the adding of buildings is done before the removing, I moved the adding-code above the removing-code.

    I btw also wrote a Python version of this and it got accepted in 108 ms!


  • 0
    O
    This post is deleted!

  • 0

    @ourlord: You are wrong. So wrong. My solution does not produce those false points, it correctly outputs only [[0 1], [2 0]]. Furthermore, your proposed change is so obviously wrong because you check liveBlg.top().second even when liveBlg is empty and then it crashes! Even for your own example input! Are you serious? Please always test before making such accusations.


  • 0
    O

    I didn't look at the code so clearly I apologize. Your code works well for sure. I don't know why I pointed out that problem 2 hours ago.


  • 0
    A

    Why python is faster?


  • 0

    @akluffy2 Click the link.


  • 0
    J

    @StefanPochmann
    Hi StvFanPochmann,

    Thank you so much for the link. Besides this one, there are 2 questions on leetcode that their C/C++ solution is much slower than python and java. No.56:Insert Interval and No.57: Merge Intervals.


  • -2
    Q
    This post is deleted!

  • 0
    T

    To be honest, this solution is the most amazing one I've seen. Just curious about how you came up with it. At the first time when I was analyzing this problem, there were like thousands of cases needed to be handled. Good thinking!


  • 4
    T

    Just say this could be helpful for understanding. Code adapted from above.

    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int>> res;
            priority_queue<pair<int,int>> heap;// first: height, second, endTime
            int cur = 0;
            int size = buildings.size();
            while(cur<size || !heap.empty()){
                int curX;
                // Case 1: No intesection with previous Max height building
                if(cur==size || !heap.empty()&&heap.top().second<buildings[cur][0]){
                    curX = heap.top().second;
                    // Find the downstair for the previous max height building
                    while(!heap.empty()&&heap.top().second<=curX)  heap.pop();
                }
                
                // Case 2: Intersection with previous Max height building
                else{
                    curX = buildings[cur][0];
                    // Add all new buildings (height, rightEnd) to the heap, to find the maxHeight
                    while(cur<size && buildings[cur][0]==curX){
                        heap.push(std::make_pair(buildings[cur][2], buildings[cur][1]));
                        cur++;
                    }
                }
                int curH = (heap.empty()) ? 0 : heap.top().first;
                if(res.empty()||res.back().second!=curH)  res.push_back(make_pair(curX, curH));
            }
            return res;
        }
    };
    

  • 0
    M

    Thanks for posting such a nice solution! Just one suggestion to make it neater, you can use curly braces to create the pair instead of using make_pair in C++11.


  • 0
    D
    This post is deleted!

Log in to reply
 

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