I write this piece of shit but get 98% beats (cpp)


  • 0

    The main idea just seems as the highest voted essay but has a little tricky part, using heap to save right corners of rectangles. This code meant to very simple and clean, but I waste most of my time and code on handling the corner cases, those overlapped points and many left corners on the same line, those are so nasty!!!! Anyway, I worked it out and don't want to touch it anymore!

    vector<pair<int,int>> getSkyline(vector<vector<int>> &buildings){
        if(buildings.empty()) return{};
        vector<pair<int,int>> ret;
        auto cmp = [](pair<int,int>&a, pair<int,int> &b){
            return a.second<b.second||(a.second==b.second&&a.first<=b.first);
        };
        priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> pq(cmp);
        pq.push({INT_MAX,0});
        for(vector<int> &b:buildings){
            while(pq.top().first<b[0]){//must be '<' instead of '<=' because we need to handle right corner coincidently overlap with a left corner;
                int pos = pq.top().first; pq.pop();
                if(pos>ret.back().first){
                    ret.push_back({pos,pq.top().second});//add a right corner if it's not covered skyline;
                }else{
                    ret.back().second = pq.top().second;//let the y of right corner decrease to the right position;
                }
            }
            while(!ret.empty()&&b[0]==ret.back().first&&ret.back().second<b[2]) ret.pop_back();//kill those points just under current left corner;
            if(pq.top().second<b[2]) ret.push_back({b[0],b[2]}); //make sure current left corner point is covered by skyline via checking highest right corner in pq.
            if(pq.top().second==b[2]&&pq.top().first==b[0]) pq.pop(); //if there's a right corner coincidently overlap with a left corner, we need to make it look like a line!
            pq.push({b[1],b[2]});
        }
        while(pq.size()>1){
            int pos = pq.top().first; pq.pop();
            if(pos>ret.back().first){
                ret.push_back({pos,pq.top().second});
            }else{
                ret.back().second = pq.top().second;
            }
        }
        return ret;
    }
    

Log in to reply
 

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