Skip to content

391. Perfect Rectangle

Jump to bottom
Jacky Zhang edited this page Sep 30, 2016 · 1 revision

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.

解题思路为：

Perfect Rectangle需要满足以下条件：

  1. 组成的大方块的面积等于所有小方块的面积和。
  2. 对于每个小方块的四个角，除了组成的最大方块的四个角不与任何角重合，其他的角要么是两个方块重合，要么是四个方块重合。
  3. 对于一个重合的角，必须是各方块的不同位置的角(top-left, top-right, bottom-left, bottom-right)。

因此可以给一个方块的四个角编号，(bottom-left: 1, bottom-right: 2, top-right: 4, top-left: 8)，方便做位运算。 采用hash map来存储所有的corner和它们的type，如果一个corner是多个方块重合的，则通过或操作来更新type，若存在编号相同的情况，则不是perfect rectangle。 最后，type为1，2，4，8的corner即为最后组成的大方块的四个角。 因此最后判断两个条件：

  1. type为1，2，4，8的corner是否为4个；
  2. 大方块的面积是否等于所有小方块的面积之和。

如果都成立，则为perfect rectangle。

public class Solution {
    Map<String, Integer> map = new HashMap<>();
    
    public boolean isRectangleCover(int[][] rectangles) {
        int lx = Integer.MAX_VALUE, ly = Integer.MAX_VALUE;
        int rx = Integer.MIN_VALUE, ry = Integer.MIN_VALUE;
        int sum = 0;
        for(int[] rect : rectangles) {
            lx = Math.min(lx, rect[0]);
            ly = Math.min(ly, rect[1]);
            rx = Math.max(rx, rect[2]);
            ry = Math.max(ry, rect[3]);
            sum += (rect[2] - rect[0]) * (rect[3] - rect[1]);
            if(isOverlap(rect[0]+" "+rect[1], 1)
            || isOverlap(rect[2]+" "+rect[1], 2)
            || isOverlap(rect[2]+" "+rect[3], 4)
            || isOverlap(rect[0]+" "+rect[3], 8)) return false;
        }
        int count = 0;
        for(Integer type : map.values()) {
            if(type == 1 || type == 2 || type == 4 || type == 8) count++;
        }
        return count == 4 && sum == (rx - lx) * (ry - ly);
    }
    
    private boolean isOverlap(String corner, int pos) {
        Integer type = map.get(corner);
        if(type == null) {
            type = pos;
        } else {
            if((type & pos) != 0) return true;
            else type |= pos;
        }
        map.put(corner, type);
        return false;
    }
}
Clone this wiki locally