Scan solution in c++(850ms)


  • 1
    F
    the basic idea : scan from left to right, check the most left edge. 
    

    if the edage is the left of some rectangle, if the rectangle is the topmost, we will probably add a new line segment to the result and add it to a set(when we reach the right edge, we will remove it).

    if the edge is the right, we will remove it from the set and add(update) the result.

    struct cmp 
    {
    	cmp(vector<vector<int>>* p, bool t)
    	{
    		p_ = p;
    		t_ = t;
    	}
    	bool operator ()(const int i, const int j) const
    	{
    		if(t_)
    		{
    			const vector<int>& v1 = p_->at(i);
    			const vector<int>& v2 = p_->at(j);
    			if(v1[2] != v2[2]) return v1[2] < v2[2];
    
    			return v1[1] < v2[1];
    		}
    		return p_->at(i)[1] > p_->at(j)[1];
    	}
    	vector<vector<int> >*	p_;
    	bool					t_;
    };
    vector<pair<int, int>> getSkyline(vector<vector<int>>& b) 
    {
    	typedef pair<int, int> point;
    	vector<point> res;
    
    	if(b.empty()) return res;
    
    	int size = (int)b.size();
    	point pt;
    	
    	cmp ch(&b, true);
    	cmp cr(&b, false);
    
    	priority_queue<int, vector<int>, cmp> qh(ch), qr(cr);
    
    	int i = 0;
    	// from left to right, scan the most left house.
    	while(i < size || !qr.empty())
    	{
    		//choose one from the heap
    		if(i == size || (!qr.empty() && b[qr.top()][1] < b[i][0]))
    		{
    			int idx = qr.top();
    			qr.pop();
    
    			while(!qh.empty() && b[qh.top()][0] == -1)
    				qh.pop();				
    
    			if(idx == qh.top()) //highest one
    			{
    				qh.pop();
    				while(!qh.empty() && b[qh.top()][0] == -1)
    					qh.pop();
    
    				// got the second highest one, if not, height is 0
    				point pt = !qh.empty() ? point(b[idx][1], b[qh.top()][2]) : point(b[idx][1], 0);
    
    				if(!res.empty() && res.back().first == pt.first && res.back().second > pt.second)
    					res.back().second = pt.second;
    				else
    					res.push_back(pt);
    			}
    			else 
    			{
    				b[idx][0] = -1;// marked as deleted.(also, the qh,qr can be replaced with set)
    			}
    		}
    		else // new rectangle
    		{
    			if(i > 0 && b[i - 1] == b[i])
    			{
    				++i;
    				continue;
    			}
    			qh.push(i);
    			qr.push(i);
    			if(qh.top() == i)// highest one
    			{
    				if(!res.empty() && res.back().second == b[i][2])
    					;
    				else if(!res.empty() && res.back().first == b[i][0])
    					res.back().second = b[i][2];
    				else
    					res.push_back(point(b[i][0], b[i][2]));
    			}
    			++i;
    		}
    	}
    	return res;
    }

Log in to reply
 

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