Runway | Topcoder Archive

Problem Statement

Our mile-long airport runway needs to be inspected. We have made patches on it over the last year. The patches that have been completely covered by later patches so that no area is left exposed don't have to be inspected, but all the other patches do.

Create a class Runway that contains a method inspect that is given int[]s x0 and x1 indicating the locations of the patches and that returns the number of patches that must be inspected.

The ith elements of x0 and x1 refer to the end positions of a single patch. The elements are given in chronological order with earlier patches before later patches. A patch includes its endpoints and all the area between them. A patch whose endpoints are both the same has NO area and never needs to be inspected.

Definition

Class:: Runway
Method:: inspect
Parameters:: int[], int[]
Returns:: int
Method signature:: int inspect(int[] x0, int[] x1)
(be sure your method is public)

Constraints

x0 and x1 will have the same number of elements, between 1 and 50 inclusive.
Each element of x0 and of x1 will be between 0 and 5280 inclusive.

Examples

```
{3,4,0,2,100,5280}
```
```
{7,2,6,50,500,0}
```
```
Returns: 1
```
That last patch covered the entire runway. The earlier patches do not have to be inspected since they are entirely hidden.
```
{2,6,2}
```
```
{6,3,3}
```
```
Returns: 2
```
The patches between 6 and 3, and between 2 and 3 are visible, and completely cover the earlier patch from 2 to 6.
```
{1,2,3,4,5,6}
```
```
{1,2,3,4,5,6}
```
```
Returns: 0
```
These are six separate patches, but none of them have any area so no patches are visible.
```
{4,7,6,5,4}
```
```
{6,7,6,5,4}
```
```
Returns: 1
```

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.