C++ line sweep algorithm with very detailed explanation - very good for beginners.


  • 0
    G
    class Solution {
    public:
        
        struct Point{
          int x;
          int h;
          bool start;
            
          Point(int c, int height,bool isStart):
            x(c),h(height),start(isStart){}
        };
        
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            multiset<int> tree;
            vector<Point> v;
            vector<pair<int,int> > result;
            int maxSoFar = 0;
            tree.insert(0);
            
            for(auto &b : buildings){
                //create two end points one for start and one for end
                Point p1 = {b[0],b[2],true};
                Point p2 = {b[1],b[2],false};
                v.push_back(p1);
                v.push_back(p2);
            }
            
            //sort the endpoints while addressing edge cases:
            //1. if the x coordinates are different choose the point with the lesser x coordinate
            //2. otherwise, 
            //2.a if both point are start points choose the higher point
            //2.b if both points are end points choose the lower point
            //2.c if one is start and one is end - choose the start to come first
            
            sort(v.begin(),v.end(),[](const Point &p1, const Point &p2)->bool{
               if(p1.x < p2.x){
                   return true;
               } 
               else if(p1.x == p2.x){
                   if(p1.start && p2.start){
                       return p1.h > p2.h;
                   }
                   else if(!p1.start && !p2.start){
                       return p1.h < p2.h;
                   }
                   else{
                       return p1.start;
                   }
               }
                
               return false;
            });
            
            //traverse the sorted points and insert/remove them from the multiset
            for(auto &p : v){
                
                //if this is a start point & its hieght is bigger than the hieghst point currently in our set
                // add this point to the result (notice that in the begining the first height in the tree is 0).
                
                if(p.start){
                    if(p.h > maxSoFar){
                        result.push_back({p.x,p.h});
                    }
                    
                    tree.insert(p.h);
                    maxSoFar = max(maxSoFar,p.h);
                }
                else{
                    
                    // since this is a multiset, we need to pick only one of hieghts corresponding to this point
                    auto per = tree.equal_range(p.h);
                    
                    //erase that point
                    tree.erase(per.first);
                    
                    if(maxSoFar == p.h){
                        
                        //if that point was the hieghest look at the next hieghest point left in the set
                        int newMaxSoFar = *(prev(tree.end()));
                        
                        // if they are different than add a new point to the result using the x coordinate of this point
                        // and the height of the remaining point in the set
                        // However, if they are similar, no need to add a the point to the queue as this new point is 
                        // simply a continuation of the previous building.
                        if(newMaxSoFar != maxSoFar){
                            result.push_back({p.x,newMaxSoFar});
                            maxSoFar = newMaxSoFar;
                        }
                    }
                }
            }
            
            return result;
        }
    };
    

Log in to reply
 

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