human
I found an interesting problem on https://leetcode.com/problems/rectangle-area-ii/:
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.

I tried it in Python, but could not do it. Can you solve it?

 What is a Python program to find the total area covered by all rectangles in the plane?
assistant
#Here is Python program to find the total area covered by all rectangles in the plane.

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        Xs = [x for x1, _, x2, _ in rectangles for x in [x1, x2]]
        Xs.sort()
        X_idx_lookup = {x: idx for idx, x in enumerate(Xs)}
        
        res = 0
        prev_y = 0
        X_span = 0
        
        Ys = [e for x1, y1, x2, y2 in rectangles for e in [[y1, x1, x2, 1], [y2, x1, x2, -1]]]
        Ys.sort()
        
        overlap_count = [0] * len(Xs)
        
        for y, xl, xr, inout in Ys:
            res += (y - prev_y) * X_span
            prev_y = y
            start_idx, end_idx = X_idx_lookup[xl], X_idx_lookup[xr]
            for i in range(start_idx, end_idx):
                overlap_count[i] += inout
            X_span = sum(x2 - x1 if c > 0 else 0 for x1, x2, c in zip(Xs, Xs[1:], overlap_count))
        return res % 1000000007

    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        Xs = [x for x1, _, x2, _ in rectangles for x in [x1, x2]]
        Xs.sort()
        covered = [0] * len(Xs)
        res = 0
        
        keypoints = [e for x1, y1, x2, y2 in rectangles for e in [[y1, x1, x2, 1], [y2, x1, x2, -1]]]
        keypoints.sort()
        
        prev_y = 0
        width_span = 0
        for y, x1, x2, inout in keypoints:
            res += (y - prev_y) * width_span
            prev_y = y
            for i in range(len(covered) - 1):
                a, b = Xs[i], Xs[i + 1]
                if x1 <= a and b <= x2:
                    covered[i] += inout
            width_span = sum(Xs[i + 1] - Xs[i] if covered[i] > 0 else 0 for i in range(len(covered) - 1))
        return res % 1000000007