A classic Sweep line solution with detailed comments


  • 0
    G
    class Solution {
    public:
    
    //
    // While this looks redundant it comes in handy for 
    // comparing between different points with same coordinates
    //
    struct Line
    {
        int Height;
        
        Line(int H)
        :
        Height(H)
        {}
        
    };
    
    struct Point
    {
    	int Loc;
    	bool Left;
    	Line *Ln;
    	
    	Point(int Lc, bool Lft, Line *L)
    	:
    	Loc(Lc),
    	Left(Lft),
    	Ln(L)
    	{}
    	
    };
    
    //
    // Sorting is done based first by x coordinat, then by left or right point (left first),
    // then for two points with same x and both are left we chose based on higher,
    // if two points with same x and both right we chose the shorter
    //
    friend bool operator<(const Point& p1, const Point &p2)
    {
    	return (p1.Loc < p2.Loc || (p1.Loc == p2.Loc && p1.Left == true && p2.Left != true) ||
    	    (p1.Loc == p2.Loc && p1.Left == true && p2.Left == true && p1.Ln->Height > p2.Ln->Height) ||
    	    (p1.Loc == p2.Loc && p1.Left == false && p2.Left == false && p1.Ln->Height < p2.Ln->Height));
    }
    
    
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings)
    {
    	vector<pair<int, int> > Res;
    	vector<Point> Points;
    	map<int,Line*> S;
    	int CurrMaxHeight = INT_MIN;
    
    	for (auto &B : buildings)
    	{
    		Line *L = new Line(B[2]);
    		Point Left(B[0],true,L), Right(B[1],false,L);
    		Points.push_back(Left);
    		Points.push_back(Right);
    	}
    
        //
        // Sort the buildings based on the operator< above
        //
        sort(Points.begin(),Points.end());
    	
    	for (auto &P : Points)
    	{
    		int Height = (P.Ln)->Height;
    
    		if (P.Left)
    		{
    		    //
    		    // if the Height of the current point being inserted
    		    // is higher than the Max so far, 
    		    // update the max so far first, insert this new pair into
    		    // the result vector
    		    //
    		    
    			if(Height > CurrMaxHeight)
    			{
    			    CurrMaxHeight = Height;
    			    Res.push_back(make_pair(P.Loc,CurrMaxHeight));
    			}
    			
    			//
    			// Just insert the <Height,Line> into the map
    			// Notice that there could be another pair <Height,Line2> already in the map
    			// in this case we'll override that pair with the new one.
    			// Since we already sorted based on height, this has no implications on the result
    			// but will serve as when we need to delete the line
    			//
    			
    			S[Height] = P.Ln;
    		}
    		else
    		{
    			auto Iter = S.find(Height);
    		    	
    			if(Height == CurrMaxHeight)
    			{
    			    //
    			    // if the current point's line
    			    // does not correspond to the line in the map
    			    // (which has the same height) we just ignore it.
    			    // otherwise we enter the if below
    			    //
    			    if(P.Ln == Iter->second)
    			    {
        		       //
        		       // first erase this <height,Line*> pair
        		       //
    			       S.erase(Iter);
    			       
    			       //
    			       // if this was the last pair then CurrMaxHeigth becomes 0
    			       //
    			       
    			       if(S.empty())
    			       {
    			           CurrMaxHeight = 0;;
    			       }
    			       else
    			       {
    			           //
    			           // We get the Heighest height in the map
    			           // and update our CurrMaxHeight
    			           //
    			           auto Prev = prev(S.end());
    			           CurrMaxHeight = Prev->first;
    			       }
    			       
    			       Res.push_back(make_pair(P.Loc,CurrMaxHeight));
    			    }
    			}
    			else
    			{
    			    //
    			    // we are trying to delete 
    			    // a <Height,Line*> that is lower in height than the max so far
    			    // so who cares!
    			    //
    			    
    			    if(P.Ln == Iter->second)
    			    {
    			        S.erase(Iter);
    			    }
    			}
    		}
    	}
    
    	return (Res);
    }
    };
    

Log in to reply
 

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