Share my sweeping line solution. Accidentally better than 100%


  • 0
    H

    Here is the idea:
    We sweep line from smallest x to largest x. We treat all the lines as intervals. When we reach end of any rectangle, it actually means we are removing an interval. If that is inside the big rectangle, that means some other small rectangles should begin with the ended interval.
    So, given x, there is a bunch of small intervals that end there, we merge them into remove. If it is valid big rectangle, there should be a bunch of small intervals start at that x. If we merge them into insert. Then, these 2 vectors should be same.
    Of course, the 1st intervals should always be inserting interval, and the last intervals should always be the removing intervals.

    class Solution {
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            map<int, vector<pair<int, int>>> insertIntervals;
            map<int, vector<pair<int, int>>> removeIntervals;
            for(int i=0; i<rectangles.size(); i++){
                insertIntervals[rectangles[i][0]].emplace_back(rectangles[i][1], rectangles[i][3]);
                removeIntervals[rectangles[i][2]].emplace_back(rectangles[i][1], rectangles[i][3]);
            }
    
            auto it1 = insertIntervals.begin();
            vector<pair<int,int>> tI;
            if (merge(it1->second, tI) == false || tI.size()>1)
                return false; //check the 1st line, return false if we have more than 1 intervals. 
            insertIntervals.erase(it1);  //erase the first line. 
            
            auto it2 = removeIntervals.begin();
            while(it2 != removeIntervals.end()){
                /* Idea: when we scan and we remove a bunch of intervals, we need to insert a bunch of intervals, they should be same. Only for the last set of removeIntervals there is no insertInterval*/
                vector<pair<int, int>> remove;
                if(merge(it2->second, remove) == false)
                    return false;
                if(insertIntervals.find(it2->first) == insertIntervals.end()){
                    if(removeIntervals.size()!=1) //only for the last interval the insertIntervals will not find it. 
                        return false;
                }
                else{//insertIntervals has it, it should be same as removeIntervals
                    vector<pair<int, int>> insert;
                    if(merge(insertIntervals[it2->first], insert) == false)
                        return false;
                    if(remove != insert) //compare vectors directly.
                        return false;
                    insertIntervals.erase(it2->first);
                }
                removeIntervals.erase(it2);
                it2 = removeIntervals.begin();
                //clear the removeIntervals 1 by 1.
            }
            //the insertIntervals should be empty, because each removeIntervals should remove 1 interval
            return insertIntervals.size()==0;
        }
        
        struct less_than_key
        {
            inline bool operator() (const pair<int,int>& struct1, const pair<int,int>& struct2)
            {
                return (struct1.first < struct2.first);
            }
        };
        
        /* Merge vector of pair into another vector of pair. They should be adjacent but no intersection */
        bool merge(vector<pair<int, int>> &pairs, vector<pair<int, int>> &tI){
            std::sort(pairs.begin(), pairs.end(), less_than_key());
            int curStart = pairs[0].first;
            for(int i=1; i<pairs.size(); i++){
                if(pairs[i].first < pairs[i-1].second){//there is intersection, return false
                    return false;
                }
                if(pairs[i].first > pairs[i-1].second){
                    tI.emplace_back(curStart, pairs[i-1].second);
                    curStart = pairs[i].first;
                }
            }
            tI.emplace_back(curStart, pairs[pairs.size()-1].second);
            return true;
        }
    };
    

  • 0
    H

    Actually I can change map to unordered_map, it is even faster.
    I think the solution utilize 2 facts:
    1, the input are small rectangles, there is no special shape.
    2, based on 1, if there is a rectangle starting with x, there is always same interval ending at another x. So, we only need to check that, at each x, there are always same starting intervals and ending intervals.

    Did I miss some corner cases?


Log in to reply
 

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