391.md

Perfect Rectangle

Description

link

---

Solution

The right answer must satisfy two conditions:

• the large rectangle area should be equal to the sum of small rectangles
• count of all the points should be even, and that of all the four corner points should be one

---

Code

O(n)

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        x1 = sys.maxsize
        y1 = sys.maxsize
        x2 = -sys.maxsize
        y2 = -sys.maxsize
        _set = set()
        
        area = 0
        for rect in rectangles:
            x1 = min(x1, rect[0])
            y1 = min(y1, rect[1])
            x2 = max(x2, rect[2])
            y2 = max(y2, rect[3])
            
            area += (rect[2] - rect[0]) * (rect[3] - rect[1])
            
            for x, y in itertools.product([rect[0], rect[2]], [rect[1], rect[3]]):
                if (x, y) in _set:
                    _set.remove((x, y))
                else:
                    _set.add((x, y))
        return all((x, y) in _set for x, y in itertools.product([x1, x2], [y1, y2])) and len(_set) == 4 and area == (x2 - x1) * (y2 - y1)