We are given a list of (axis-aligned) rectangles.  Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.
Find the total area covered by all rectangles in the plane.  Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: As illustrated in the picture.
Example 2:
Input: [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 = (-7)^2 = 49.
Note:
1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= rectangles[i][j] <= 10^9
The total area covered by all rectangles will never exceed 2^63 - 1 and thus will fit in a 64-bit signed integer.


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted(list(set(x for x1, y1, x2, y2 in rectangles for x in [x1, x2])))
        xs_i = {x: i for i, x in enumerate(xs)}
        
        rects = []
        for x1, y1, x2, y2 in rectangles:
            rects.append((y1, x1, x2, 1))
            rects.append((y2, x1, x2, -1))
        rects = sorted(rects)
        counts = [0] * len(xs_i)
    
        curr_y = 0
        area = 0
        L = 0
        for y, x1, x2, sig in rects:
            area += (y - curr_y) * L
            curr_y = y
            for x in range(xs_i[x1], xs_i[x2]):
                counts[x] += sig
            L = sum(x2 - x1 for x1, x2, s1 in zip(xs, xs[1:], counts) if s1 > 0 )
        return area % (10**9 + 7)


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted(list(set(x for x1, y1, x2, y2 in rectangles for x in [x1, x2])))
        xs_i = {x: i for i, x in enumerate(xs)}
        
        rects = []
        for x1, y1, x2, y2 in rectangles:
            rects.append((y1, x1, x2, 1))
            rects.append((y2, x1, x2, -1))
        rects = sorted(rects)
        counts = [0] * len(xs_i)
    
        curr_y = 0
        area = 0
        L = 0
        for y, x1, x2, sig in rects:
            area += (y - curr_y) * L
            curr_y = y
            for x in range(xs_i[x1], xs_i[x2]):
                counts[x] += sig
            L = sum(x2 - x1 for x1, x2, s1 in zip(xs, xs[1:], counts) if s1 > 0 )
        return area % (10**9 + 7)