C++ Solution using Multiset


  • 0
    S
    struct starts{
      const bool operator()(pair<int, int>&a, pair<int, int>&b){
          if(a.first == b.first)
              return a.second < b.second;
          return a.first < b.first;
      }  
    };
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& b) {
          vector<pair<int, int>>start, end, res;
            // use single array
            for(auto i : b)
            {
                // differentiate start points by making h negative
                start.push_back(make_pair(i[0], -i[2]));
                start.push_back(make_pair(i[1], i[2]));
            }
            sort(start.begin(), start.end(), starts());
            multiset<int>pq;
            pq.insert(0);
            int maxv = 0;
            for(int i = 0;i<start.size();i++ )
         {
             int pos, ht=-1;
            if(start[i].second < 0)
            {
                pq.insert(-start[i].second);
                pos = start[i].first;
                ht = -start[i].second;
            }
             else{
                // remove bldg of ht=end[i].second from pq
                 pq.erase(pq.find(start[i].second));
                 pos = start[i].first;
             }
             if(ht == -1)
                 ht = *(pq.rbegin());
             if(maxv != *(pq.rbegin()))
             {
               res.push_back(make_pair(pos, ht));
               maxv = *(pq.rbegin());
             }
         }
            return res;
        
        }
    };
    

Log in to reply
 

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