391. Perfect Rectangle
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.
算法分析
刚开始想到的一个方法是先遍历所有的矩形，找出最小的(leftMost,bottomMost)和最大的(rightMost,topMost),这是所有矩形所可能覆盖的最大的区域。然后定义一个二维数组：
int[][] area = new int[topMost-bottomMost][rightMost-leftMost],
再遍历一次所有的矩形，对矩形 rect,做如下判断：
int totalArea=0;
for(int[] rect:rectangles){
for(int i=rect[1]-bottomMost;i<rect[3]-bottomMost;i++){
for(int j=rect[0]-leftMost;j<rect[2]-leftMost;j++){
totalArea++;
if(area[i][j]>=1){//说明出现了重叠覆盖区域
return false;
}
else{
area[i][j]++;
}
}
}
当遍历完所有矩形后，首先判断
if(totalArea!=(rightMost-leftMost)*(topMost-bottomMost)){
return false;
}
因为如果要实现完全覆盖，必须有 totalArea=(rightMost-leftMost)*(topMost-bottomMost).
满足了相等条件后,再判断是否area[][]数组中所有的数据均为1----是，则说明最大覆盖区域中的每个小单元均被覆盖了一次，满足条件，返回 true；否，则说明有的区域没有覆盖到，返回 false。
上述算法的思想是正确的，但是当输入数据量覆盖面积较大时，会出现 Memory Exceeded 的错误。考虑使用一个 bit 来表示一个单元面积，结果出现了 Time Limit Exceeded 的错误。
最终考虑使用如下算法思想：
任意一个矩形均有4个顶点，当出现Perfect Rectangle时，在最大覆盖矩形内部，所有其它矩形的任意一个顶点均会出现偶数次（因为一个矩形旁边应当有一个或三个矩形和它紧密相连，那么这个相接的顶点就出现了偶数次）。所以，可以构建一个HashSet<String> set,以一个矩形的四个顶点的(x,y)坐标构造字符串 (x+","+y),以该字符串做键值，当set中不存在该键值时，则存入该键值；当set中存在该键值时，则删除该键值；最终set中应该只剩下四个键，这四个键即是最大覆盖矩形的四个顶点。
Java 算法实现如下(并不正确)：
public class Solution {
public boolean isRectangleCover(int[][] rectangles) {
if(rectangles.length==0||rectangles[0].length==0){
return false;
}
else{
HashSet<String>set=new HashSet<>();
int leftMost=Integer.MAX_VALUE;
int bottomMost=Integer.MAX_VALUE;
int rightMost=Integer.MIN_VALUE;
int topMost=Integer.MIN_VALUE;
int x1,y1,x2,y2;
for(int[] rect:rectangles){
x1=rect[0];
y1=rect[1];
x2=rect[2];
y2=rect[3];
//记录最靠边界的点的坐标
if(x1<leftMost){
leftMost=x1;
}
if(y1<bottomMost){
bottomMost=y1;
}
if(x2>rightMost){
rightMost=x2;
}
if(y2>topMost){
topMost=y2;
}
//由当前考察的矩形的四个顶点的坐标构成的键值
String key1=x1+","+y1;
String key2=x1+","+y2;
String key3=x2+","+y1;
String key4=x2+","+y2;
//删除那些出现了偶数次的键值
if(set.contains(key1)){
set.remove(key1);
}
else{
set.add(key1);
}
if(set.contains(key2)){
set.remove(key2);
}
else{
set.add(key2);
}
if(set.contains(key3)){
set.remove(key3);
}
else{
set.add(key3);
}
if(set.contains(key4)){
set.remove(key4);
}
else{
set.add(key4);
}
}
String key1=leftMost+","+bottomMost;
String key2=leftMost+","+topMost;
String key3=rightMost+","+bottomMost;
String key4=rightMost+","+topMost;
if(set.size()!=4||!set.contains(key1)||
!set.contains(key2)||!set.contains(key3)||
!set.contains(key4)){
return false;
}
else{
return true;
}
}
}
}
结果出现如下错误：
如上数据所示，[0,0,3,3] 为最大覆盖矩形，两个[1,1,2,2]又都在其内部，且互相抵消掉了，所以该输入数据成功地避开了所有的检测，返回了不正确的答案 true。 改正方法是添加一个 long area 数据用以记录所有矩形的总面积，检测 area 是否和 (rightMost-leftMost)*(topMost-bottomMost)相等，若不等，则说明没有完全覆盖或者出现了重叠覆盖，返回 false；若相等，则做进一步判断。新代码如下：
Java算法实现：
public class Solution {
public boolean isRectangleCover(int[][] rectangles) {
if(rectangles.length==0||rectangles[0].length==0){
return false;
}
else{
HashSet<String>set=new HashSet<>();
int leftMost=Integer.MAX_VALUE;
int bottomMost=Integer.MAX_VALUE;
int rightMost=Integer.MIN_VALUE;
int topMost=Integer.MIN_VALUE;
int x1,y1,x2,y2;
long area=0;
for(int[] rect:rectangles){
x1=rect[0];
y1=rect[1];
x2=rect[2];
y2=rect[3];
area+=(x2-x1)*(y2-y1);//累积记录已遍历的矩形的面积
//记录最靠边界的点的坐标
if(x1<leftMost){
leftMost=x1;
}
if(y1<bottomMost){
bottomMost=y1;
}
if(x2>rightMost){
rightMost=x2;
}
if(y2>topMost){
topMost=y2;
}
if(area>(rightMost-leftMost)*(topMost-bottomMost)){
//目前遍历的矩形的面积已经大于了所能覆盖的面积，则一定存在了重叠
return false;
}
//由当前考察的矩形的四个顶点的坐标构成的键值
String key1=x1+","+y1;
String key2=x1+","+y2;
String key3=x2+","+y1;
String key4=x2+","+y2;
//totalCouverCount用以记录是否出现了某个矩形完全覆盖了之前的某个矩形
//删除那些出现了偶数次的键值
if(set.contains(key1)){
set.remove(key1);
}
else{
set.add(key1);
}
if(set.contains(key2)){
set.remove(key2);
}
else{
set.add(key2);
}
if(set.contains(key3)){
set.remove(key3);
}
else{
set.add(key3);
}
if(set.contains(key4)){
set.remove(key4);
}
else{
set.add(key4);
}
}
if(area!=(rightMost-leftMost)*(topMost-bottomMost)){//说明没有完全覆盖或出现了重叠覆盖
return false;
}
String key1=leftMost+","+bottomMost;
String key2=leftMost+","+topMost;
String key3=rightMost+","+bottomMost;
String key4=rightMost+","+topMost;
if(set.size()!=4||!set.contains(key1)||
!set.contains(key2)||!set.contains(key3)||
!set.contains(key4)){
return false;
}
else{
return true;
}
}
}
}
这次就成功了。