Perfect Rectangle

Desicription

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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
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:

1
2
3
4
5
6
7
8
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:

1
2
3
4
5
6
7
8
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.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
bool isRectangleCover(const std::vector<std::vector<int>>& rectangles) {
int left = INT_MAX;
int right = INT_MIN;
int top = INT_MIN;
int bottom = INT_MAX;
auto set = std::set<std::pair<int, int>>{};
int sumArea = 0;
for(auto& rectangle : rectangles) {
left = std::min(left, rectangle[0]);
right = std::max(right, rectangle[2]);
top = std::max(top, rectangle[3]);
bottom = std::min(bottom, rectangle[1]);

static const auto map = std::vector<std::pair<int, int>> {
{0, 1},
{2, 3},
{2, 1},
{0, 3},
};

for(const auto& it : map) {
std::pair<int, int> currentPoint = {rectangle[it.first], rectangle[it.second]};
if(set.find(currentPoint) != set.end()) {
set.erase(currentPoint);
} else {
set.insert(currentPoint);
}
}
sumArea += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
}

return !(set.size() != 4 || set.find({left, top}) == set.end() || set.find({left, bottom}) == set.end() || set.find({right, top}) == set.end() || set.find({right, bottom}) == set.end() || sumArea != ((right - left) * (top - bottom)));
}
};