Sharing my 832ms C++ solution


  • 0
    T
    bool compare(pair<int, int> P1, pair<int, int> P2)
    {
        if(P1.first<P2.first)
            return true;
        else if(P1.first>P2.first)
            return false;
        else
            return (P1.second<P2.second);
    }
    
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            int n = buildings.size(), i;
            int left, right, height;
            vector<pair<int, long long int>> myHeights;
            for(i=0; i<n; i++)
            {
                left = buildings[i][0];
                right = buildings[i][1];
                height = buildings[i][2];
                myHeights.push_back(make_pair(left, (long long int) (-height)));
                myHeights.push_back(make_pair(right, (long long int) height));
            }
            
            sort(myHeights.begin(), myHeights.end(), compare);
            
            multiset<int> myMultiset;
            myMultiset.insert(0);
            
            n = myHeights.size();
            vector<pair<int, int>> result;
            int prevHeight=0;
            int currHeight;
            for(i=0; i<n; i++)
            {
                if(myHeights[i].second<0)
                    myMultiset.insert((int) (-myHeights[i].second));
                else
                    myMultiset.erase(myMultiset.find(myHeights[i].second));
                    
                currHeight = *myMultiset.rbegin();
                if(currHeight!=prevHeight)
                {
                    prevHeight = currHeight;
                    result.push_back(make_pair(myHeights[i].first, currHeight));
                }
            }
            
            return result;
        }
    };

Log in to reply
 

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