268. Two-Rectangle Footprint
A farmer fences two rectangular plots whose sides run exactly east-west and north-south. Each plot is given as [x1, y1, x2, y2]: the south-west corner (x1, y1) and the north-east corner (x2, y2), with x1 < x2 and y1 < y2. The plots a and b may overlap, touch, sit inside one another, or be far apart.
Return the total ground area covered by at least one of the plots, counting any shared region only once. The coordinates are small enough that the result fits a 32-bit integer. The intended method is O(1): add both areas and subtract the intersection. Marking every unit cell of the bounding box would need up to 4*10^8 steps and is far too slow.
Example 1
- Input:
- a = [0,0,4,3], b = [2,1,7,5]
- Output:
- 28
- Explanation:
The areas are 12 and 20 and they share a 2 x 2 region, so 12 + 20 - 4 = 28.
Example 2
- Input:
- a = [-5,-5,-2,-2], b = [3,3,6,9]
- Output:
- 27
- Explanation:
The plots are disjoint, so the areas 9 and 18 simply add up to 27.
Example 3
- Input:
- a = [1,1,9,9], b = [3,4,5,6]
- Output:
- 64
- Explanation:
The second plot lies inside the first, so only the 64 units of the first plot count.
Constraints
a.length = b.length = 4
-104 ≤ x1 < x2 ≤ 104 and -104 ≤ y1 < y2 ≤ 104 for each rectangle
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 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(1)
- Space
- O(1)