题目描述：

LeetCode 391. Perfect Rectangle

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.

 

题目大意：

给定N个与坐标轴对齐的矩形（其中N > 0），判断它们是否恰好围成一个矩形区域。

每一个矩形通过左下角和右上角的坐标表示。例如，一个单位正方形用[1,1,2,2]表示。（左下角坐标(1, 1)，右上角坐标(2, 2)）.

测试用例如题目描述。

解题思路：

解法I “顶点检查法”：

参考LeetCode Discuss，链接地址：

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

利用points记录各个顶点被矩形的覆盖情况

记矩形的左下、右下、右上、左上顶点为A、B、C、D，则有：

左下顶点A的坐标为(l, b)
右下顶点B的坐标为(r, b)
右上顶点C的坐标为(r, t)
左上顶点D的坐标为(l, t)

如下图所示：

        G
D |-----|-----| C
  |     |     |  
H |-----I-----| F
  |     |     |  
A |-----|-----| B
        E

将左下A、右下B、右上C、左上D分别标号为1、2、4、8（这样标号便于位运算），则有：

points[A] |= 1
points[B] |= 2
points[C] |= 4
points[D] |= 8

points[E] = points[A] | points[B] = 3 （左下顶点、右下顶点的并）
points[F] = points[B] | points[C] = 6 （右下顶点、右上顶点的并）
points[G] = points[C] | points[D] = 12 （右上顶点、左上顶点的并）
points[H] = points[A] | points[D] = 9 （左下顶点、左上顶点的并）
points[I] = points[A] | points[B] | points[C] | points[D] = 15（四个顶点的并）

Python代码：

class Solution(object):
    def isRectangleCover(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        left = min(x[0] for x in rectangles)
        bottom = min(x[1] for x in rectangles)
        right = max(x[2] for x in rectangles)
        top = max(x[3] for x in rectangles)

        points = collections.defaultdict(int)
        for l, b, r, t in rectangles:
            A, B, C, D = (l, b), (r, b), (r, t), (l, t)
            for p, q in zip((A, B, C, D), (1, 2, 4, 8)):
                if points[p] & q: return False
                points[p] |= q

        for px, py in points:
            if left < px < right or bottom < py < top:
                if points[(px, py)] not in (3, 6, 9, 12, 15):
                    return False
        return True

解法II 扫描线法

参阅LeetCode Discuss：https://discuss.leetcode.com/topic/55944/o-n-log-n-sweep-line-solution

本文链接：http://bookshadow.com/weblog/2016/08/28/leetcode-perfect-rectangle/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码