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.
class Solution {
// 1. Exact 4 corners
// 2. Other shared points must occur evenly (cannot be odd)
// 3. sum(area) = area of 4 corners enclosed areas
private String delimiter = ",";
public boolean isRectangleCover(int[][] rectangles) {
MapString, Integer set = new HashMap();
MapString, int[] map2 = new HashMap();
int sum = 0;
for (int i = 0; i rectangles.length; i++) {
sum = sum + (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
// bottom-left
String blKey = generateKey(rectangles[i][0], rectangles[i][1]);
if (set.containsKey(blKey)) {
map2.remove(blKey);
}
else {
map2.put(blKey, new int[]{rectangles[i][0], rectangles[i][1]});
}
set.put(blKey, set.getOrDefault(blKey, 0) + 1);
// top-right
String trKey = generateKey(rectangles[i][2], rectangles[i][3]);
if (set.containsKey(trKey)) {
map2.remove(trKey);
}
else {
map2.put(trKey, new int[]{rectangles[i][2], rectangles[i][3]});
}
set.put(trKey, set.getOrDefault(trKey, 0) + 1);
//top-left
String tlKey = generateKey(rectangles[i][0], rectangles[i][3]);
if (set.containsKey(tlKey)) {
map2.remove(tlKey);
}
else {
map2.put(tlKey, new int[]{rectangles[i][0], rectangles[i][3]});
}
set.put(tlKey, set.getOrDefault(tlKey, 0) + 1);
//bottom-right
String brKey = generateKey(rectangles[i][2], rectangles[i][1]);
if (set.containsKey(brKey)) {
map2.remove(brKey);
}
else {
map2.put(brKey, new int[]{rectangles[i][2], rectangles[i][1]});
}
set.put(brKey, set.getOrDefault(brKey, 0) + 1);
}
if (map2.size() == 4) {
for (String key: set.keySet()) {
if (set.get(key) % 2 != 0 set.get(key) != 1) {
return false;
}
}
int maxL = Integer.MIN_VALUE;
int minL = Integer.MAX_VALUE;
int maxW = Integer.MIN_VALUE;
int minW = Integer.MAX_VALUE;
for (String key : map2.keySet()) {
if(map2.get(key)[0] maxL) {
maxL = map2.get(key)[0];
}
if(map2.get(key)[0] minL) {
minL = map2.get(key)[0];
}
if(map2.get(key)[1] maxW) {
maxW = map2.get(key)[1];
}
if(map2.get(key)[1] minW) {
minW = map2.get(key)[1];
}
}
System.out.println("Sum: " + sum);
System.out.println("Area: " + (maxL - minL) * (maxW - minW));
if(sum == (maxL - minL) * (maxW - minW)) {
return true;
}
}
return false;
}
private String generateKey(int i, int j) {
return Integer.toString(i) + delimiter + Integer.toString(j);
}
}