clean C++ sweep line solution


  • 3
    H

    A naive solution to the problem is to check rectangles pairwisely for overlap. Then compare the sum of areas of all rectangles to the area of its bounding box.

    But the pairwise comparison is too slow. This is where the sweep line solution comes in to quickly check overlap of many rectangles. This is by scanning vertical edges of rectangles in the order of x, and maintaining an ordered list of y-intervals. Left edges are inserted into the intervals before which interval overlap is checked. Right edges are removed from the intervals.

    A complication here is that right edges should be processed before all left edges. I deal this problem by mapping x coordinate to time t with: t = 2x+1 for left edges and t = 2x for right edges.

    struct interval {
        int start;
        int end;
        interval(int start_, int end_) : start(start_), end(end_) {};
    };
    
    struct edge {
        int t;
        interval i;
        edge(int t_, interval i_) : t(t_), i(i_) {};
    };
    
    struct interval_cmp {
       bool operator()(interval i1, interval i2) { return i1.start < i2.start; }; 
    };
    
    struct edge_cmp {
       bool operator()(edge e1, edge e2) { return e1.t > e2.t; }; 
    };
    
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        priority_queue<edge, vector<edge>, edge_cmp>  q;
        set<interval, interval_cmp> active_intervals;
        
        int minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN;
        int area = 0;
        for (const auto& rect : rectangles) {
            area += (rect[2]-rect[0])* (rect[3]-rect[1]);
            minx = min(rect[0], minx);
            miny = min(rect[1], miny);
            maxx = max(rect[2], maxx);
            maxy = max(rect[3], maxy);
            q.emplace(rect[0]*2+1, interval(rect[1], rect[3]));
            q.emplace(rect[2]*2  , interval(rect[1], rect[3]));
        }
        
        while (!q.empty()) {
            int t = q.top().t;
            interval i = q.top().i;
            if (t % 2) { //insert interval
                auto it = active_intervals.lower_bound(i);
                if (it != active_intervals.begin() && prev(it)->end > i.start) return false;
                if (it != active_intervals.end() && it->start < i.end) return false;
                active_intervals.insert(it, i);
            }
            else { //remove interval
                active_intervals.erase(i);
            }
            q.pop();
        }
        return area == (maxx-minx) * (maxy - miny);
    }
    

  • 1
    S

    you can use negative number to represent right edge.


  • 0
    C

    I think it is not an O(NlogN) solution, though. prev is an O(N) operation inside the loop.


Log in to reply
 

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