Rectangle Area II

arraysegment treesweep line

Problem Statement

You are given a 2D array of axis-aligned rectangles . Each rectangle[i] = [x _i1 , y _i1 , x _i2 , y _i2 ] denotes the i ^th rectangle where (x _i1 , y _i1 ) are the coordinates of the bottom-left corner , and (x _i2 , y _i2 ) are the coordinates of the top-right corner .

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once .

Return the total area . Since the answer may be too large, return it modulo 10 ^9 + 7 .

Examples

Example 1

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

Example 2

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
The answer is 10 ^18 modulo (10 ^9 + 7), which is 49.

Constraints

1 <= rectangles.length <= 200

rectanges[i].length == 4

0 <= x _i1 , y _i1 , x _i2 , y _i2 <= 10 ^9

x _i1 <= x _i2

y _i1 <= y _i2

All rectangles have non zero area.

😤

Hard

Difficulty

Topic Info

ModuleDSA

CategoryArray

Sub-topicSegment Tree