KRectangleIntersection | Topcoder Archive

Problem Statement

You are given four int[]s, each with the same number of elements: xl, yl, xh, and yh. These describe a collection of rectangles. The sides of each rectangle are parallel to the coordinate axes. For each valid index i, one of the rectangles has its lower left corner at (xl[i], yl[i]) and its upper right corner at (xh[i], yh[i]).

Given an int k, find the largest possible area of the intersection of k of these rectangles.

Definition

Class:: KRectangleIntersection
Method:: maxIntersection
Parameters:: int[], int[], int[], int[], int
Returns:: long
Method signature:: long maxIntersection(int[] xl, int[] yl, int[] xh, int[] yh, int k)
(be sure your method is public)

Constraints

xl, yl, xh, yh will all have the same number of elements.
The number of elements in xl will be between 1 and 200, inclusive.
Each element in xl, yl, xh, yh will be between 1 and 10^9, inclusive.
For each valid i, xl[i] will be smaller than xh[i] and yl[i] will be smaller than yh[i] .
k will be between 1 and the number of rectangles, inclusive.

Examples

```
{1, 2, 3}
```
```
{1, 2, 3} 
```
```
{10, 9, 8}
```
```
{10, 9, 8}
```
```
2
```
```
Returns: 49
```
Three rectangles: one with corners at (1,1) and (10,10), one with corners at (2,2) and (9,9), and one with corners at (3,3) and (8,8). The optimal solution is clearly to take the first two rectangles.
```
{2, 5, 1}
```
```
{3, 7, 1}
```
```
{7, 10, 6}
```
```
{9, 10, 5}
```
```
2
```
```
Returns: 8
```
The optimal solution is to choose rectangles 0 and 2 (using 0-based indices). The intersection area would be a rectangle with bottom left corner at (2, 3) and top right corner at (6, 5) having an area of (6-2) * (5-3) = 4 * 2 = 8.
```
{2, 5, 1}
```
```
{3, 7, 1}
```
```
{7, 10, 6}
```
```
{9, 10, 5}
```
```
1
```
```
Returns: 30
```
The intersection of one rectangle is the rectangle itself. The biggest of these rectangles is rectangle 0. Its area is 5 * 6 = 30.
```
{2, 5, 1}
```
```
{3, 7, 1}
```
```
{7, 10, 6}
```
```
{9, 10, 5}
```
```
3
```
```
Returns: 0
```
The only subset of size 3 is the whole set which has an empty intersection. The area of an empty intersection is 0.

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.