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.

Refer to https://discuss.leetcode.com/topic/56052/really-easy-understanding-solution-o-n-java

and   https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination

Idea

Consider how the corners of all rectangles appear in the large rectangle if there's a perfect rectangular cover.

Rule1: The local shape of the corner has to follow one of the three following patterns

• • Corner of the large rectangle (blue): it occurs only once among all rectangles
  • T-junctions (green): it occurs twice among all rectangles
  • Cross (red): it occurs four times among all rectangles

For each point being a corner of any rectangle, it should appear even times except the 4 corners of the large rectangle. So we can put those points into a hash map and remove them if they appear one more time.

At the end, we should only get 4 points. 

Rule2:  the large rectangle area should be equal to the sum of small rectangles

1 public class Solution { 2     public boolean isRectangleCover(int[][] rectangles) { 3         if (rectangles==null || rectangles.length==0 || rectangles[0].length==0) return false; 4         int subrecAreaSum = 0;  //sum of subrectangle's area 5         int x1 = Integer.MAX_VALUE; //large rectangle bottom left x-axis 6         int y1 = Integer.MAX_VALUE; //large rectangle bottom left y-axis 7         int x2 = Integer.MIN_VALUE; //large rectangle top right x-axis 8         int y2 = Integer.MIN_VALUE; //large rectangle top right y-axis 9         10         HashSet
     
       set = new HashSet
      
       (); // store points11         12         for(int[] rec : rectangles) {13             //check if it has large rectangle's 4 points14             x1 = Math.min(x1, rec[0]);15             y1 = Math.min(y1, rec[1]);16             x2 = Math.max(x2, rec[2]);17             y2 = Math.max(y2, rec[3]);18             19             //calculate sum of subrectangles20             subrecAreaSum += (rec[2]-rec[0]) * (rec[3] - rec[1]);21             22             //store this rectangle's 4 points into hashSet23             String p1 = Integer.toString(rec[0]) + "" + Integer.toString(rec[1]);24             String p2 = Integer.toString(rec[0]) + "" + Integer.toString(rec[3]);25             String p3 = Integer.toString(rec[2]) + "" + Integer.toString(rec[1]);26             String p4 = Integer.toString(rec[2]) + "" + Integer.toString(rec[3]);27             28             if (!set.add(p1)) set.remove(p1);29             if (!set.add(p2)) set.remove(p2);30             if (!set.add(p3)) set.remove(p3);31             if (!set.add(p4)) set.remove(p4);32         }33         34         if (set.size()!=4 || !set.contains(x1+""+y1) || !set.contains(x1+""+y2) || !set.contains(x2+""+y1) || !set.contains(x2+""+y2))35             return false;36         return subrecAreaSum == (x2-x1) * (y2-y1);37     }38 }