850. Rectangle Area II (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def rectangleArea(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: int
        """
        ys = set()
        for rect in rectangles:
            ys.add(rect[1])
            ys.add(rect[3])
        ys = sorted(list(ys))
        
        def getWidth(xs):
            w = 0
            xs.sort()
            start, end = xs[0]
            for a, b in xs:
                if a > end:
                    w += end - start
                    start = a
                end = max(end, b)
            w += end - start
            return w
        
        result = 0
        for i, y in enumerate(ys[:-1]):
            xs, length = [], 0
            for x1, y1, x2, y2 in rectangles:
                if y1 <= y < y2:
                    xs.append([x1, x2])
            if xs:
                length = getWidth(xs)
                result += length * (ys[i + 1] - y)
            
        return result % (10**9 + 7)