SoManyRectangles
SRM 729 · 2018-02-08 · by erinn
Problem Statement
Several rectangles are on the plane, some possibly overlapping others. The rectangles are described in
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.
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.
{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.
Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SoManyRectangles with a public method int maxOverlap(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2) · 41 test cases · 2 s / 256 MB per case