Perfect rectangle problem

We have N rectangles aligned with the axes, whereN > 0And determine whether they can accurately cover a rectangular area. Each rectangle is represented by the coordinates of the point in the lower left and the point in the upper right. For example, a unit square can be represented by,1,2,2 [1]. The coordinates of the point in the lower left corner are(1, 1)And the point on the upper right is zero(2, 2)).

Example 1:

,1,3,3 rectangles = [[1], [3,1,4,2], [3,2,4,4],,3,2,4 [1], [2,3,3,4]] returns true. Five rectangles together can precisely cover a rectangular area.Copy the code

Example 2:

,1,2,3 rectangles = [[1],,3,2,4 [1], [3,1,4,2], [3,2,4,4]] returns false. There is an interval between two rectangles that cannot cover a rectangle.Copy the code

Example 3:

,1,3,3 rectangles = [[1], [3,1,4,2],,3,2,4 [1], [3,2,4,4]] returns false. There is a gap at the top of the figure that cannot cover a rectangle.Copy the code

Example 4:

,1,3,3 rectangles = [[1], [3,1,4,2],,3,2,4 [1], [2,2,4,4]] returns false. Because there are intersecting areas in the middle, although it forms a rectangle, it's not exactly covered.Copy the code

What is a perfect rectangle? According to the description of the title, if all the small rectangles given can form a perfect rectangle, the following conditions must be met:

  • The shape of all the smaller rectangles is still a rectangle
  • The formed rectangle must not have overlapping or vacant parts

Using the first example given in the question, the case for a given small rectangle is shown as follows:


As shown in the figure above, the five small rectangles given just make up a large rectangle, whose lower left and upper right coordinates are [1,1] and [4,4] respectively. There is no overlap between the rectangles and no gaps in the middle of the larger rectangles. If you look at other examples, you’ll see why it doesn’t make a perfect rectangle.

So how do you determine that a given example satisfies this requirement? For a single rectangle, it contains two elements: point and area. If we want to make a perfect rectangle, first of all, the sum of the areas of all the little rectangles has to equal the area of the perfect rectangle. To know the area of a perfect rectangle, you must first know the coordinates of the lower left corner [X1,Y1] and the upper right corner [X2,Y2]. [X1,Y1] is the lower left corner of all the small rectangles, and [X2,Y2] is the upper right corner of all the small rectangles. Given [X1,Y1] and [X2,Y2], the area of the perfect rectangle must be calculated, and the corresponding result can be true only if the sum of the areas of the small rectangles is equal to the area of the perfect rectangle.

But the same area is only promising for a perfect rectangle, and maybe a final sound. As shown below, all the smaller rectangles make up a large rectangle, with exactly one unit overlap, although there is a vacancy of one unit. Therefore, it seems feasible to judge purely from the equal area, but it is obviously unable to meet the requirements.


Therefore, we also need to make further judgment from the point of view. Here is a legal example shown on the left and an illegal example shown on the right, with numbers marking the number of occurrences of vertices contained in all small rectangular packages. It can be found that in the legal example, the vertex with occurrence number 1 is the four vertices of the final perfect rectangle, and the other vertices all appear twice. In the illegal case, the number one vertex is not just the four vertices of a perfect rectangle.


Therefore, we can record the occurrence of vertices while traversing the small rectangle. If the current vertex has not been traversed, it is added to the set, otherwise it is removed from the set. If the final set contains only four vertices of a possible perfect rectangle, then the example is valid; otherwise, a perfect rectangle cannot be formed.

Summary, if the solution to the problem need to traverse all the small rectangular, traversal process need to wait until the lower left corner of the perfect rectangle and the upper right corner of the coordinates, the sum of the rectangular area, and the emergence of the vertex, and finally, to determine whether the sum of small rectangular area and perfect the sum of the rectangular area is equal, whether the collection contains only four vertices and four vertices is perfect rectangular, You have to satisfy both of these conditions to make a perfect rectangle.

The decoding code is as follows:

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        // Coordinates of the lower left and upper right corners of the perfect rectangle
        int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE;
        int X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
		
        // The sum of the areas of small rectangles
        int areas = 0;
        // Record the occurrence of all vertices
        Set<String> points = new HashSet<>();
        for (int[] rectangle : rectangles) {
            int x1 = rectangle[0], y1 = rectangle[1], x2 = rectangle[2], y2 = rectangle[3];
            // Update the coordinates
            X1 = Math.min(x1, X1);
            Y1 = Math.min(y1, Y1);
            X2 = Math.max(x2, X2);
            Y2 = Math.max(y2, Y2);

            areas += (x2 - x1) * (y2 - y1);
            // Determine whether vertices occur
            String[] ps = {x1 + "" + y1, x2 + "" + y2, x1 + "" + y2, x2 + "" + y1};
            for (String s : ps) {
                // Do not appear, add; Otherwise, remove
                if(points.contains(s)){
                    points.remove(s);
                } else{ points.add(s); }}}// Are the areas equal
        int expected = (X2 - X1) * (Y2 -Y1);
        if(areas ! = expected){return false;
        }
        // Whether the vertex case is satisfied
        if(points.size() ! =4| |! points.contains(X1 +""+ Y1) || ! points.contains(X2 +""+ Y2) || ! points.contains(X1 +""+ Y2) || ! points.contains(X2 +"" + Y1)){
            return false;
        }
        return true; }}Copy the code