1419. Double-Layer Area
A greenhouse roof is tiled with rectangular plastic sheets. Sheet i is rects[i] = [x, y, w, h] and occupies the half-open region from x up to but not including x + w, and from y up to but not including y + h. Sheets may overlap in any way, and edge contact alone is not an overlap.
Insulation matters wherever at least two sheets lie on top of each other. Return the total area of the region that is covered by two or more sheets, counting each point once no matter how many sheets cover it, as a 64-bit integer. With up to 20000 sheets and coordinates up to 10^4 a per-cell tally is far too slow; aim for O(n log n) time and O(n) space.
Example 1
- Input:
- rects = [[1,1,2,2],[2,2,2,2]]
- Output:
- 1
- Explanation:
The sheets overlap only on the unit square from (2, 2) to (3, 3), so the area is 1.
Example 2
- Input:
- rects = [[1,1,2,2]]
- Output:
- 0
- Explanation:
A single sheet never has a second layer, so the answer is 0.
Example 3
- Input:
- rects = [[1,1,3,3],[1,1,3,3],[1,1,3,3]]
- Output:
- 9
- Explanation:
Three identical 3 by 3 sheets are stacked, so the whole area of 9 is doubly covered.
Constraints
1 ≤ n ≤ 2 * 104; 1 ≤ x, y, w, h ≤ 104.
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)