Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/391.html
Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).
Return true if all the rectangles together form an exact cover of a rectangular region.
Example 1:
Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] Output: true Explanation: All 5 rectangles together form an exact cover of a rectangular region.
Example 2:
Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]] Output: false Explanation: Because there is a gap between the two rectangular regions.
Example 3:
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]] Output: false Explanation: Because two of the rectangles overlap with each other.
Constraints:
1 <= rectangles.length <= 2 * 104rectangles[i].length == 4-105 <= xi, yi, ai, bi <= 105
Algorithm
When considering a rectangle, its four vertices can only have three attributes: blue, green, and red. The blue attribute means there are no other rectangles adjacent to the vertex, while the T-shaped green attribute means two rectangles are adjacent to each other and the red attribute means four rectangles are adjacent to each other.
For a perfect rectangle, there can only be four blue points, which is a critical criterion. The vertices of the rectangle are labeled as 1, 2, 4, and 8 in the order of bottom left, top left, top right, and bottom right. Using these labels in binary format (1=0001, 2=0010, 4=0100, 8=1000) allows for convenient bitwise OR operations.
Another important criterion is that if a point is the lower-left vertex of a certain rectangle, it cannot be the lower-left vertex of any other rectangles. To check this condition for each vertex, we record its attributes. If a vertex has the same attribute as another vertex in a different rectangle, we return false. Using the binary labels for each vertex allows us to check their attributes bit by bit.
If the attributes of each point do not conflict, we then verify whether the mask of each point is reasonable. We know that each point can only have one of the three attributes: blue, green, or red. A blue point has only one 1 in its four-bit mask, and there can only be four blue points. A green point has two 1s in its mask, and there can be six possible masks. A red point has four 1s in its mask, and there can only be one such mask.
To check whether the masks are valid, we count the number of masks with attributes 1, 2, 4, and 8, or indirectly count the number of green and red dots to ensure that there are four blue points in total. The last condition is that the total area of all rectangles must equal the area of the original large rectangle. This can be calculated by finding the minimum lower-left point and the maximum upper-right point of all rectangles.
Code
-
import java.util.HashSet; public class Perfect_Rectangle { 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; } } } } } ############ class Solution { public boolean isRectangleCover(int[][] rectangles) { long area = 0; int minX = rectangles[0][0], minY = rectangles[0][1]; int maxX = rectangles[0][2], maxY = rectangles[0][3]; Map<Pair, Integer> cnt = new HashMap<>(); for (int[] r : rectangles) { area += (r[2] - r[0]) * (r[3] - r[1]); minX = Math.min(minX, r[0]); minY = Math.min(minY, r[1]); maxX = Math.max(maxX, r[2]); maxY = Math.max(maxY, r[3]); cnt.merge(new Pair(r[0], r[1]), 1, Integer::sum); cnt.merge(new Pair(r[0], r[3]), 1, Integer::sum); cnt.merge(new Pair(r[2], r[3]), 1, Integer::sum); cnt.merge(new Pair(r[2], r[1]), 1, Integer::sum); } if (area != (long) (maxX - minX) * (maxY - minY) || cnt.getOrDefault(new Pair(minX, minY), 0) != 1 || cnt.getOrDefault(new Pair(minX, maxY), 0) != 1 || cnt.getOrDefault(new Pair(maxX, maxY), 0) != 1 || cnt.getOrDefault(new Pair(maxX, minY), 0) != 1) { return false; } cnt.remove(new Pair(minX, minY)); cnt.remove(new Pair(minX, maxY)); cnt.remove(new Pair(maxX, maxY)); cnt.remove(new Pair(maxX, minY)); return cnt.values().stream().allMatch(c -> c == 2 || c == 4); } private static class Pair { final int first; final int second; Pair(int first, int second) { this.first = first; this.second = second; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Pair pair = (Pair) o; return first == pair.first && second == pair.second; } @Override public int hashCode() { return Objects.hash(first, second); } } } -
class Solution: def isRectangleCover(self, rectangles: List[List[int]]) -> bool: area = 0 minX, minY = rectangles[0][0], rectangles[0][1] maxX, maxY = rectangles[0][2], rectangles[0][3] cnt = defaultdict(int) for r in rectangles: area += (r[2] - r[0]) * (r[3] - r[1]) minX = min(minX, r[0]) minY = min(minY, r[1]) maxX = max(maxX, r[2]) maxY = max(maxY, r[3]) cnt[(r[0], r[1])] += 1 cnt[(r[0], r[3])] += 1 cnt[(r[2], r[3])] += 1 cnt[(r[2], r[1])] += 1 if ( area != (maxX - minX) * (maxY - minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, maxY)] != 1 or cnt[(maxX, minY)] != 1 ): return False del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, maxY)], cnt[(maxX, minY)] return all(c == 2 or c == 4 for c in cnt.values()) ############ import heapq class Solution(object): def isRectangleCover(self, rectangles): """ :type rectangles: List[List[int]] :rtype: bool """ leftBound = rectangles[0][0] rightBound = rectangles[0][2] bottomBound = rectangles[0][1] topBound = rectangles[0][3] lines = [] realArea = 0 for rect in rectangles: leftBound = min(leftBound, rect[0]) rightBound = max(rightBound, rect[2]) bottomBound = min(bottomBound, rect[1]) topBound = max(topBound, rect[3]) realArea += (rect[3] - rect[1]) * (rect[2] - rect[0]) lines.append((rect[0], 1, rect[1], rect[3])) lines.append((rect[2], -1, rect[1], rect[3])) area = (rightBound - leftBound) * (topBound - bottomBound) if area != realArea: return False lines.sort() bst = [] for line in lines: x, flag, bottom, top = line if flag > 0: idx = bisect.bisect_right(bst, (bottom, top)) bisect.insort_right(bst, (bottom, top)) if idx + 1 < len(bst) and bst[idx + 1][0] < bst[idx][1] or idx > 0 and bst[idx][0] < bst[idx - 1][1]: return False else: bst.remove((bottom, top)) return area == realArea -
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isRectangleCover(vector<vector<int>>& rectangles) { long long area = 0; int minX = rectangles[0][0], minY = rectangles[0][1]; int maxX = rectangles[0][2], maxY = rectangles[0][3]; using pii = pair<int, int>; map<pii, int> cnt; for (auto& r : rectangles) { area += (r[2] - r[0]) * (r[3] - r[1]); minX = min(minX, r[0]); minY = min(minY, r[1]); maxX = max(maxX, r[2]); maxY = max(maxY, r[3]); ++cnt[{r[0], r[1]}]; ++cnt[{r[0], r[3]}]; ++cnt[{r[2], r[3]}]; ++cnt[{r[2], r[1]}]; } if (area != (long long) (maxX - minX) * (maxY - minY) || cnt[{minX, minY}] != 1 || cnt[{minX, maxY}] != 1 || cnt[{maxX, maxY}] != 1 || cnt[{maxX, minY}] != 1) { return false; } cnt.erase({minX, minY}); cnt.erase({minX, maxY}); cnt.erase({maxX, maxY}); cnt.erase({maxX, minY}); return all_of(cnt.begin(), cnt.end(), [](pair<pii, int> e) { return e.second == 2 || e.second == 4; }); } }; -
type pair struct { first int second int } func isRectangleCover(rectangles [][]int) bool { area := 0 minX, minY := rectangles[0][0], rectangles[0][1] maxX, maxY := rectangles[0][2], rectangles[0][3] cnt := make(map[pair]int) for _, r := range rectangles { area += (r[2] - r[0]) * (r[3] - r[1]) minX = min(minX, r[0]) minY = min(minY, r[1]) maxX = max(maxX, r[2]) maxY = max(maxY, r[3]) cnt[pair{r[0], r[1]}]++ cnt[pair{r[0], r[3]}]++ cnt[pair{r[2], r[3]}]++ cnt[pair{r[2], r[1]}]++ } if area != (maxX-minX)*(maxY-minY) || cnt[pair{minX, minY}] != 1 || cnt[pair{minX, maxY}] != 1 || cnt[pair{maxX, maxY}] != 1 || cnt[pair{maxX, minY}] != 1 { return false } delete(cnt, pair{minX, minY}) delete(cnt, pair{minX, maxY}) delete(cnt, pair{maxX, maxY}) delete(cnt, pair{maxX, minY}) for _, c := range cnt { if c != 2 && c != 4 { return false } } return true } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b }