Perfect Rectangle

题目来源
给一堆矩形左下和右上坐标，问这些能否恰好拼成一个大矩形。
我只想到最naive的方法，先算出左下角和右上角的坐标，然后构建一个大vector，然后再遍历一遍，所有被覆盖的都改为1。然后判断，代码如下：

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        pair<int, int> bottomLeft = make_pair(INT_MAX, INT_MAX), TopRight = make_pair(0, 0);
        int n = rectangles.size();
        int area = 0;
        for (int i=0; i<n; i++) {
            if (rectangles[i][0] <= bottomLeft.first && rectangles[i][1] <= bottomLeft.second)
                bottomLeft = make_pair(rectangles[i][0], rectangles[i][1]);
            if (rectangles[i][2] >= TopRight.first && rectangles[i][3] >= TopRight.second)
                TopRight = make_pair(rectangles[i][2], rectangles[i][3]);
            area += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
        }
        for (int i=0; i<n; i++) {
            if (rectangles[i][0] < bottomLeft.first || rectangles[i][1] < bottomLeft.second
                || rectangles[i][2] > TopRight.first || rectangles[i][3] > TopRight.second)
                return false;
        }
        int deltaX = (TopRight.first - bottomLeft.first), deltaY = (TopRight.second - bottomLeft.second);
        if (deltaX * deltaY != area)
            return false;
        vector<vector<int>> isContained(deltaX, vector<int>(deltaY, 0));
        for (int i=0; i<n; i++) {
            for (int x=rectangles[i][0]; x<rectangles[i][2]; x++)
                for (int y=rectangles[i][1]; y<rectangles[i][3]; y++) {
                    if (isContained[x-bottomLeft.first][y-bottomLeft.second])
                        return false;
                    isContained[x-bottomLeft.first][y-bottomLeft.second]++;
                }
        }
        return true;
    }
};

然后又不出意料的超时了，而且内存也爆炸了。怎么改进呢？
看了半天卧槽，效率真的是低的令人发指。
满足题目要求需要满足几个条件：

• 大矩形面积等于小矩形面积和；
• 除了最边上四个点唯一，其余点都重复2次或4次。

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int x1 = INT_MAX, y1 = INT_MAX, x2 = INT_MIN, y2 = INT_MIN;
        int n = rectangles.size();
        int area = 0;
        set<pair<int, int>> sets;
        for (int i=0; i<n; i++) {
            if (!sets.insert(make_pair(rectangles[i][0], rectangles[i][1])).second)
                sets.erase(make_pair(rectangles[i][0], rectangles[i][1]));
            if (!sets.insert(make_pair(rectangles[i][2], rectangles[i][3])).second)
                sets.erase(make_pair(rectangles[i][2], rectangles[i][3]));
            if (!sets.insert(make_pair(rectangles[i][0], rectangles[i][3])).second)
                sets.erase(make_pair(rectangles[i][0], rectangles[i][3]));
            if (!sets.insert(make_pair(rectangles[i][2], rectangles[i][1])).second)
                sets.erase(make_pair(rectangles[i][2], rectangles[i][1]));
            if (rectangles[i][0] <= x1 && rectangles[i][1] <= y1) {
                x1 = rectangles[i][0];
                y1 = rectangles[i][1];
            }
            if (rectangles[i][2] >= x2 && rectangles[i][3] >= y2) {
                x2 = rectangles[i][2];
                y2 = rectangles[i][3];
            }
            area += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
        }
        for (int i=0; i<n; i++) {
            if (rectangles[i][0] < x1 || rectangles[i][1] < y1
                || rectangles[i][2] > x2 || rectangles[i][3] > y2)
                return false;
        }
        if (sets.count(make_pair(x1, y1)) != 1 || sets.count(make_pair(x1, y2)) != 1
            || sets.count(make_pair(x2, y1)) != 1 || sets.count(make_pair(x2, y2)) != 1 || sets.size() != 4)
            return false;
        return (x2 - x1) * (y2 - y1) == area;
    }
};