391. 完美矩形

exiaohu 于 2021-11-16 发布

题目链接：391. 完美矩形

扫描线。

精确填充，当且仅当每个区域都被填充一次。使用扫描线将区域切割成若干小区域：

  1. 遍历给出的每个矩形，若对某个小区域填充2次，则非完美矩形；
  2. 若每个矩形遍历后，对还存在没有被填充的区域，则非完美举行；
  3. 否则是完美矩形。
from typing import List


class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        x1s, y1s, x2s, y2s = zip(*rectangles)
        xs = {x: i for i, x in enumerate(sorted(set(x1s + x2s)))}
        ys = {y: i for i, y in enumerate(sorted(set(y1s + y2s)))}

        visited = [[False for _ in range(len(ys) - 1)] for _ in range(len(xs) - 1)]

        for x1, y1, x2, y2 in rectangles:
            i1, j1, i2, j2 = xs[x1], ys[y1], xs[x2], ys[y2]
            for i in range(i1, i2):
                for j in range(j1, j2):
                    if visited[i][j]:
                        return False
                    visited[i][j] = True

        return all(all(row) for row in visited)