Rectangle Union Area

Problem

Given axis-aligned rectangles as [x1, y1, x2, y2], return the total area covered by their union, counting overlaps only once.

Compress the x coordinates into strips, and for each strip merge the y intervals of all rectangles that fully span it. Add width times merged height for every strip.

Hint

Merging y intervals inside each x strip handles any amount of overlap.

Test cases

case 1

in: [[[0,0,2,2],[1,1,3,3]]]

expected: 7

case 2

in: [[[0,0,2,2],[2,0,4,2]]]

expected: 8

case 3

in: [[[0,0,1,1]]]

expected: 1

case 4

in: [[]]

expected: 0

case 5

in: [[[0,0,3,3],[1,1,2,2]]]

expected: 9

Starter codePython

def rectangle_union_area(rectangles):
    # Your code here
    pass

5 test cases · run your code against them in the editor