TopCoder problem "Runway" used in TCO06 Qual 2/10/13 (Division I Level One)



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

0)
    
{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.
1)
    
{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.
2)
    
{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.
3)
    
{4,7,6,5,4}
{6,7,6,5,4}
Returns: 1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4517

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9898&pm=4517

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Simple Search, Iteration