Line Sweeping Algorithm. Easier than I thought


  • 0
    J

    I got the idea from https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ and https://discuss.leetcode.com/topic/39416/guaranteed-really-detailed-and-good-perfect-explanation-of-the-skyline-problem.

    The code turns out to be simpler than I expect. Probably because we don't have to create our own BST class in this case. The set<> is enough.

    struct EndPoint {
        int x;
        int h;
        int i; // index into buildings array
        EndPoint(int a, int b, int c)
        {
            x = a;
            h = b;
            i = c;
        }
    };
    
    class comparison {
    public:
        bool operator()(const EndPoint & a, const EndPoint & b)
        {
            return a.x < b.x || (a.x == b.x && a.h < b.h);
        }
    };
    
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int> > ret;
            set<pair<int, int> > s; // first: height, second: x
            vector<EndPoint> v;
            for(int i=0;i<buildings.size();i++)
            {
                v.push_back(EndPoint(buildings[i][0], buildings[i][2], i));
                v.push_back(EndPoint(buildings[i][1], buildings[i][2], i));
            }
            
            sort(v.begin(), v.end(), comparison());
            
            int idx = 0;
            while(idx < v.size())
            {
                int currX = v[idx].x;
                int currH = 0;
                while(v[idx].x == currX)
                {
                    if(buildings[v[idx].i][0] == v[idx].x) // start point
                    {
                        s.emplace(v[idx].h, v[idx].x);
                    }
                    else // end point
                    {
                        s.erase(make_pair(v[idx].h, buildings[v[idx].i][0]));
                    }
                    idx++;
                }
                
                if(!s.empty())
                {
                    auto it = --s.end();
                    currH = it->first;
                }
                
                if(ret.size() == 0 || currH != ret.back().second)
                {
                    ret.push_back(make_pair(currX, currH));
                }
            }
            
            return ret;
        }
    };
    

Log in to reply
 

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