963. Covered Floor Area
A tiling crew has laid rectangular rugs on a huge flat floor, and rugs may overlap in any way. Each rug is rectangles[i] = [x1, y1, x2, y2], where (x1, y1) is its bottom-left corner and (x2, y2) its top-right corner, with sides parallel to the axes and x1 < x2, y1 < y2.
Return the total area of floor that is covered by at least one rug, counting an area that lies under several rugs only once. Since the area can be as large as 10^18, return it modulo 1000000007. Rugs that only touch along an edge add no shared area.
Example 1
- Input:
- rectangles = [[0,0,4,2],[2,1,6,3]]
- Output:
- 14
- Explanation:
Each rectangle covers 4 x 2 = 8 units. They overlap in the block x 2..4, y 1..2 of area 2, so the union is 8 + 8 - 2 = 14.
Example 2
- Input:
- rectangles = [[0,0,2,5],[1,0,4,1],[3,3,5,6]]
- Output:
- 18
- Explanation:
Areas are 10, 3 and 6. The first two share x 1..2, y 0..1 (area 1) and the third rectangle touches neither, so the union is 10 + 3 + 6 - 1 = 18.
Constraints
- 1 ≤ rectangles.length ≤ 105
- 0 ≤ x1 < x2 ≤ 109 and 0 ≤ y1 < y2 ≤ 109
- The answer is returned modulo 1000000007
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)