We are given a set of axis-aligned rectangles and need to find the total area they cover on the 2D plane. Rectangles can overlap, and we must not double-count any overlapping region. If two rectangles share a region, that region counts once toward the total area, not twice.

The analogy is painting rectangles on a wall. Painting the same spot twice still leaves one layer of paint, so the area painted is the area of the union, not the sum of the individual rectangle areas.

The coordinates can be up to 10^9, so the answer itself can be large, which is why we return it modulo 10^9 + 7. The large coordinate range also rules out building a grid over every possible coordinate. We need approaches whose cost depends on the number of rectangles, not the size of the coordinate space.

Key Constraints:

Intuition

Inclusion-exclusion gives a direct formula for the union area. The area of the union of sets A1, A2, ..., An is: add all individual areas, subtract all pairwise intersections, add back all triple intersections, and continue alternating signs.

The intersection of any subset of axis-aligned rectangles is itself a rectangle, or empty, so each term is cheap to compute. The cost comes from the number of terms: inclusion-exclusion sums over 2^n subsets. With n up to 200, 2^n is far too large, so this approach is infeasible at the full constraint.

For small n (roughly n <= 20), it works and is simple to reason about. We iterate over all non-empty subsets, compute the intersection rectangle, and add or subtract its area based on whether the subset size is odd or even.

Algorithm

Example Walkthrough

Take rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]], the three rectangles R0, R1, R2.

Single rectangles (added, odd size): R0 has area 4, R1 has area 3, R2 has area 2. Running sum = 4 + 3 + 2 = 9.

Pairwise intersections (subtracted, even size):

Running sum = 9 - 2 - 1 - 1 = 5.

Triple intersection (added, odd size): R0, R1, R2 share x in [1,2], y in [0,1], area = 1. Running sum = 5 + 1 = 6.

The total is 6, matching the expected answer. Each overlapping region was counted exactly once after the alternating signs cancelled the double-counting.

Code

The exponential number of subsets makes this approach impractical for n = 200. The next approach avoids subsets entirely: it cuts the plane into non-overlapping cells along the rectangle boundaries and counts which cells are covered.

Intuition

With at most 200 rectangles, there are at most 400 distinct x-coordinates and 400 distinct y-coordinates. Drawing a line through every one of these values divides the plane into a grid of at most 399 x 399 cells. Every cell in this grid is either entirely inside at least one rectangle or entirely outside all of them. No cell is partially covered.

This holds because the cell boundaries are exactly the rectangle boundaries. A rectangle edge can only fall on a grid line, never through the middle of a cell, so a rectangle either contains a cell completely or misses it completely.

The plan: collect all distinct x and y coordinates, sort them, form the compressed grid, and for each cell check whether any rectangle covers it. If one does, add that cell's actual area, computed from the original coordinates, to the answer.

Algorithm

Example Walkthrough

Code

This passes for the given constraints, but the triple nested loop re-checks every rectangle against every cell. The next approach removes one of those loops by sweeping a vertical line from left to right and tracking which y-intervals are active, so each x-strip is measured once instead of cell by cell.

Intuition

Instead of checking every cell independently, we can sweep a vertical line from left to right across the plane. At each x-coordinate where something changes (a rectangle starts or ends), we update our knowledge of which y-intervals are currently active, and compute the area contribution between consecutive x-coordinates.

Treat each rectangle as two events: an "open" event at x1 (the rectangle starts contributing to y-coverage) and a "close" event at x2 (the rectangle stops contributing). As we sweep left to right, we maintain the total y-length covered by at least one active rectangle. The area between two consecutive x-coordinates is that covered y-length multiplied by the x-distance.

To compute the total covered y-length, we use coordinate compression on the y-axis. We create events sorted by x-coordinate, and for each x-interval, we determine which y-intervals are covered by checking a count array that tracks how many rectangles cover each compressed y-interval.

Algorithm

Example Walkthrough

Code