1389. Union Perimeter
A print shop lays rectangular stickers on a wall. Sticker i is described by rects[i] = [x, y, w, h] and covers the closed region from x to x + w horizontally and from y to y + h vertically. Stickers may overlap, touch along an edge, or sit inside one another.
Return the total length of the outline of the combined shape as a 64-bit integer. Every boundary counts, including the edges of any hole enclosed by the stickers. An edge shared by two touching stickers is interior to the combined shape and is not counted. With up to 20000 stickers a cell-by-cell fill is too slow; aim for O(n log n) time and O(n) space.
Example 1
- Input:
- rects = [[1,1,2,2]]
- Output:
- 8
- Explanation:
A single 2 by 2 square has perimeter 8.
Example 2
- Input:
- rects = [[1,1,2,2],[3,1,2,2]]
- Output:
- 12
- Explanation:
The squares touch along x = 3 and form a 4 by 2 rectangle with perimeter 12.
Example 3
- Input:
- rects = [[1,1,3,3],[2,2,3,3]]
- Output:
- 16
- Explanation:
The overlapping squares form a staircase shape whose outline equals that of its 4 by 4 bounding box, 16.
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)