Area Covered by Overlapping Rectangles

Hard

Some axis-aligned rectangles lie on a plane. Rectangle rects[i] = [x1, y1, x2, y2] has its bottom-left corner at (x1, y1) and its top-right corner at (x2, y2). Find the total area they cover. Any region covered by more than one rectangle counts only once. The answer can be very large, so return it modulo 10⁹ + 7.

Example 1

rects=[[0, 0, 4, 2], [2, 1, 5, 4]] → 15

The areas are 8 and 9; the shared piece from (2, 1) to (4, 2) has area 2 and counts once: 8 + 9 - 2 = 15.

Example 2

rects=[[1, 1, 3, 3], [0, 0, 6, 6]] → 36

The small rectangle lies entirely inside the big one, so the answer is the big one's area, 36.

Example 3

rects=[[0, 0, 100000, 100000]] → 999999937

The area 10¹⁰ is taken modulo 10⁹ + 7.

Constraints

1 ≤ len(rects) ≤ 200
len(rects[i]) = 4
0 ≤ x1, y1, x2, y2 ≤ 10⁹
x1 < x2, y1 < y2

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Segment Tree Array Ordered Set Line Sweep

Similar problems

City Block Outline Hard Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard A Dark Gap Between Street Lamps Hard

Input

rects=[[0, 0, 4, 2], [2, 1, 5, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 97 tests on the server, hidden ones included.