391. Perfect Rectangle

Description

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

Note

Method 1:

compare Area, and check occurance of four conner points.

Method 2:

Sweep from left to right (priority Queue) + set to check y range interval + height is same as weight.

Code

Method 1

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        bool rst = true;
        int x1 = INT_MAX, x2 = INT_MIN, y1 = INT_MAX, y2 = INT_MIN;
        set<pair<int, int>> tracker;
        int area = 0;
        for(auto rect : rectangles) {
            x1 = min(rect[0], x1);
            x2 = max(rect[2], x2);
            y1 = min(rect[1], y1);
            y2 = max(rect[3], y2);

            area += (rect[2] - rect[0]) * (rect[3] - rect[1]);

            auto pr = make_pair(rect[0], rect[1]);
            if(tracker.end() != tracker.find(pr)) {
                tracker.erase(pr);
            }
            else {
                tracker.insert(pr);
            }

            pr = make_pair(rect[0], rect[3]);
            if(tracker.end() != tracker.find(pr)) {
                tracker.erase(pr);
            }
            else {
                tracker.insert(pr);
            }

            pr = make_pair(rect[2], rect[1]);
            if(tracker.end() != tracker.find(pr)) {
                tracker.erase(pr);
            }
            else {
                tracker.insert(pr);
            }

            pr = make_pair(rect[2], rect[3]);
            if(tracker.end() != tracker.find(pr)) {
                tracker.erase(pr);
            }
            else {
                tracker.insert(pr);
            }
        }

        cout << area << "=" << (x2 - x1) * (y2 - y1) << ":" << tracker.size() << endl;
        if(area != (x2 - x1) * (y2 - y1) || tracker.size() != 4 || tracker.end() == tracker.find(make_pair(x1, y1)) || tracker.end() == tracker.find(make_pair(x1, y2)) || tracker.end() == tracker.find(make_pair(x2, y1)) || tracker.end() == tracker.find(make_pair(x2, y2))) {
            rst = false;
        }
        return rst;
    }
};