题目要求
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.
用一个二维数组来表示一堆矩形，二维数组中的每一行分别记录矩形左下角和右上角的坐标。试判断这些矩形拼接成的新的图形是否还是一个矩形。如果矩形存在重合，则不构成矩形，见图例 4.
思路和代码
这是一道纯粹的考验思维的一道题目。首先我们知道，这些矩形如果能够拼接成一个大的矩形，那么大的矩形的左下角坐标一定是所有矩形中最小的 x1 和 y1 值构成的，同理，右上角坐标一定是由最大的 x2 和 y2 的值构成的。该理想情况下矩形的面积应当等于所有矩形的面积之和。一旦不相等，则一定无法构成大的矩形。
其次，光判断面积并不足够，可以这样三个矩形构成的图形 [1,1,2,2],[2,2,3,3],[2,1,3,3]。可以看到该图形的理想矩形就是一个 2 * 2 的正方形，它的面积与所有的小矩形的和相等，但是这些小矩形并没有构成该理想的矩形。那么我们能用什么方式来过滤掉这种矩形呢。只能从矩形的顶点入手了。我们知道，任何一个能够构成理想矩形的小矩形，一定会有顶点的重合，直到只剩下四个重合度为 1 的点，即大矩形的四个顶点。其它的所有顶点都应当有另一个矩形与其重合。因此我们只需要留下所有度为 1 的顶点，判断其是否都是大矩形的四个顶点即可。
代码如下：
public boolean isRectangleCover(int[][] rectangles) {
if(rectangles==null || rectangles.length == 0 || rectangles[0].length == 0) return false;
int areaSum = 0;
int x1 = Integer.MAX_VALUE;
int x2 = Integer.MIN_VALUE;
int y1 = Integer.MAX_VALUE;
int y2 = Integer.MIN_VALUE;
Set<String> points = new HashSet<>(rectangles.length * 4);
for(int[] rectangle : rectangles) {
x1 = Math.min(rectangle[0], x1);
x2 = Math.max(rectangle[2], x2);
y1 = Math.min(rectangle[1], y1);
y2 = Math.max(rectangle[3], y2);
areaSum += (rectangle[0] – rectangle[2]) * (rectangle[1] – rectangle[3]);
String s1 = rectangle[0] + ” ” + rectangle[1];
String s2 = rectangle[0] + ” ” + rectangle[3];
String s3 = rectangle[2] + ” ” + rectangle[1];
String s4 = rectangle[2] + ” ” + rectangle[3];
if (!points.add(s1)) {
points.remove(s1);
}
if (!points.add(s2)) {
points.remove(s2);
}
if (!points.add(s3)) {
points.remove(s3);
}
if (!points.add(s4)) {
points.remove(s4);
}
}
if(!points.contains(x1 + ” ” + y1) ||
!points.contains(x1 + ” ” + y2) ||
!points.contains(x2 + ” ” + y1) ||
!points.contains(x2 + ” ” + y2) ||
points.size() != 4) return false;
return areaSum == (x2 – x1) * (y2 – y1);
}