EntertainingSegment | Topcoder Archive

Problem Statement

A long straight road goes from city A to city B. There are several radio stations along the road, and their ranges are described by the int[]s left and right. The i-th radio station can be heard at any point on the road between left[i] and right[i] kilometers from city A, inclusive.

A segment of the road is called entertaining if at least k radio stations can be heard at all points on the segment. Return the length of the longest entertaining segment of the road. If there is no such segment, return 0.

Definition

Class:: EntertainingSegment
Method:: longestEntertainingSegment
Parameters:: int[], int[], int
Returns:: int
Method signature:: int longestEntertainingSegment(int[] left, int[] right, int k)
(be sure your method is public)

Constraints

left will contain between 1 and 50 elements, inclusive.
left and right will contain the same number of elements.
Each element of left will be between 1 and 1000000000 (109), inclusive.
Each element of right will be between 1 and 1000000000 (109), inclusive.
Each element of left will be strictly less than the corresponding element of right.
k will be between 1 and 50, inclusive.

Examples

```
{1, 4, 3, 7}
```
```
{5, 8, 7, 10}
```
```
2
```
```
Returns: 5
```
The longest entertaining segment here is from 3 to 8.
```
{1}
```
```
{1000000000}
```
```
1
```
```
Returns: 999999999
```
```
{1, 3}
```
```
{3, 5}
```
```
2
```
```
Returns: 0
```
There is no entertaining segment here.
```
{1,1,4,4}
```
```
{2,2,6,6}
```
```
2
```
```
Returns: 2
```
The ranges of radio stations can coincide.
```
{1}
```
```
{2}
```
```
2
```
```
Returns: 0
```
There are not enough radio stations to form an entertaining segment.

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.