Coding Interview Questions: No. 27 - Area of Rectangles
Problem: Please implement a function which gets area of a set of rectangles, whose edges are parallel to X-axis or Y-axis.
We get all x-values of the three rectangles, which are X1, X2, …, X6 in Figure 2, and then split the merged shape into five rectangles based on x-values.
Since ranges of x-values and y-values are necessary information to calculate area, we can define a class Range:
Read full article from Coding Interview Questions: No. 27 - Area of Rectangles
Problem: Please implement a function which gets area of a set of rectangles, whose edges are parallel to X-axis or Y-axis.
We get all x-values of the three rectangles, which are X1, X2, …, X6 in Figure 2, and then split the merged shape into five rectangles based on x-values.
We should merge y-values of rectangles in ranges of x-value. For instance, both Rect1 and Rect2 fill into the x-value range between X2 and X3. Therefore, we should merge the y-value range of Rect1 and Rect2 to calculate the rectangle piece between X2 and X3.
 |
Figure 2: Split rectangles into pieces based on x-values
|
The overall algorithm to calculate the area of overlapping rectangles is: We firstly get all x-values of all rectangles, and then check whether every rectangle fills into each range formed by two neighboring x-values. If there are multiple rectangles fill into an x-value range, we merge their ranges of y-value before we calculate the area of a piece of merged rectangle.
The following function GetArea implements this algorithm. For optimization purpose, we sort all input rectangles according to their x-values of right edges, and sort a vector of all x-values.
Read full article from Coding Interview Questions: No. 27 - Area of Rectangles
