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

  • 0
    class Solution {
        struct Point{
          int x;
          int h;
          bool start;
          Point(int c, int height,bool isStart):
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            multiset<int> tree;
            vector<Point> v;
            vector<pair<int,int> > result;
            int maxSoFar = 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};
            //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;
                       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.h > maxSoFar){
                    maxSoFar = max(maxSoFar,p.h);
                    // 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
                    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){
                            maxSoFar = newMaxSoFar;
            return result;

Log in to reply

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