Участник:F.Nikitin/PerfectRectangle

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/perfect-rectangle/

class Solution:
    def isRectangleCover(self, rectangles):
        l_b = rectangles[0][0]
        r_b = rectangles[0][2]
        b_b = rectangles[0][1]
        t_b = rectangles[0][3]
        lines = []
        gt_area = 0
        for rect in rectangles:
            l_b = min(l_b, rect[0])
            r_b = max(r_b, rect[2])
            b_b = min(b_b, rect[1])
            t_b = max(t_b, rect[3])
            gt_area += (rect[3] - rect[1]) * (rect[2] - rect[0])
            lines.append((rect[0], 1, rect[1], rect[3]))
            lines.append((rect[2], -1, rect[1], rect[3]))
        area = (r_b - l_b) * (t_b - b_b)
        if area != gt_area:
            return False
        lines.sort()
        bst = []
        for line in lines:
            x, flag, bottom, top = line
            if flag > 0:
                idx = bisect.bisect_right(bst, (bottom, top))
                bisect.insort_right(bst, (bottom, top))
                if idx + 1 < len(bst) and bst[idx + 1][0] < bst[idx][1] or idx > 0 and bst[idx][0] < bst[idx - 1][1]:
                    return False
            else:
                bst.remove((bottom, top))
        return area == gt_area