Rectangle Area - Overlapping intervals expand idea from 1D
Problem Statement:
Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two rectangles.
The first rectangle is defined by its bottom-left corner (ax1, ay1)
and its top-right corner (ax2, ay2)
.
The second rectangle is defined by its bottom-left corner (bx1, by1)
and its top-right corner (bx2, by2)
.
Example 1:
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2 Output: 45
Example 2:
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2 Output: 16
Constraints:
-104 <= ax1 <= ax2 <= 104
-104 <= ay1 <= ay2 <= 104
-104 <= bx1 <= bx2 <= 104
-104 <= by1 <= by2 <= 104
Solution:
First let us solve the problem in 1D: Given Two intervals (a1,a2) and (b1,b2) find if they are overlapping or not Well, the answer is they are overlapping if
bool overlap = a1 < b2 && a2 > b1;
What is the length of this overlap? Well the length of overlap is
int L_overlap= min(a2,b2) - max(a1,b1);
So, what is the total length
int L1 = (a2-a1), L2 = (b2-b1);
int L_total = (overlap ? L1+L2-L_overlap : L1+L2);
Now we will expand this idea to 2D. The only crucial difference is that the overlap happens only if the overlap condition is met in both X and Y directions.
C++ code:
class Solution {
public:
int area(int x1, int y1, int x2, int y2)
{
return (x2-x1) * (y2-y1);
}
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int A = area(ax1,ay1,ax2,ay2);
int B = area(bx1,by1,bx2,by2);
bool overlap_x = bx1 < ax2 && bx2 > ax1;
bool overlap_y = by1 < ay2 && by2 > ay1;
if (!overlap_x || !overlap_y) return A + B;
int cx1 = max(ax1,bx1);
int cy1 = max(ay1,by1);
int cx2 = min(ax2,bx2);
int cy2 = min(ay2,by2);
int C = area(cx1,cy1,cx2,cy2);
return A + B - C;
}
};