SoManyRectangles | Topcoder Archive

Problem Statement

Several rectangles are on the plane, some possibly overlapping others. The rectangles are described in ints x1, y1, x2 and y2. Rectangle i has it's lower-left corner (x1[i], y1[i]), and upper-right corner (x2[i], y2[i]).

Two or more rectangles overlap if they have a common area. Meeting along an edge or a corner only is not an overlap. Return the largest number of rectangles that overlap in a single location.

Definition

Class:: SoManyRectangles
Method:: maxOverlap
Parameters:: int[], int[], int[], int[]
Returns:: int
Method signature:: int maxOverlap(int[] x1, int[] y1, int[] x2, int[] y2)
(be sure your method is public)

Notes

Multiple rectangles that share a non-zero common area are considered to be overlapping. As an example, if A overlaps with B and B overlaps with C, but A does not overlap with C, then the answer is 2.

Constraints

x1 will contain between 1 and 50 elements, inclusive.
x1, y1, x2, and y2 will contain the same number of elements.
x1[i] will be less than x2[i], for all valid i.
y1[i] will be less than y2[i], for all valid i.
All elements of x1, y1, x2 and y2 will be between -10^9 and 10^9, inclusive.

Examples

```
{0, 50}
```
```
{0, 50}
```
```
{100, 60}
```
```
{100, 60}
```
```
Returns: 2
```
There are two rectangles here: (0,0)-(100,100) and (50,50)-(60,60) The second rectangle completely overlaps the first.
```
{0, 90}
```
```
{0, 90}
```
```
{100, 200}
```
```
{100, 200}
```
```
Returns: 2
```
The two rectangles still overlap. It is not necessary for any of them to completely overlap.
```
{0, 100}
```
```
{0, 100}
```
```
{100, 200}
```
```
{100, 200}
```
```
Returns: 1
```
Here the two rectangles meet at a corner, but do not actually have an overlap.

{0, 0, 0, 0, 0}

{0, 0, 0, 0, 0}

{1, 1, 1, 1, 1}

{1, 1, 1, 1, 1}

Returns: 5

They are small, but all five overlap perfectly.

```
{0}
```
```
{0}
```
```
{1}
```
```
{1}
```
```
Returns: 1
```
There's only one rectangle.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.