#850
Rectangle Area II
expert · 1275 · lc hard +32 · verified · 56% accepted · 1,043 likes · top 50%
Description
You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] defines rectangle i, with bottom-left corner (xi1, yi1) and top-right corner (xi2, yi2).
Compute the total area of the plane covered by at least one rectangle. Overlapping regions are counted only once.
Return the result modulo 109 + 7.
Example 1:
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: 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
Explanation: The answer is 1018 modulo (109 + 7), which is 49.
Code
1
2
3