TopCoder problem "RoadWork" used in TCCC '03 NE/SE Regional (Division I Level Two)



Problem Statement

    Federal repaving contracts have been awarded to various contractors to fix a number of sections of the nation's highway system. Each contract specifies a single section, giving its starting and ending location. The number of feet of highway in that section is the ending location minus the starting location. For example, a section whose start is 2000 and whose end is 2001 is just one foot long. We need software to protect the public from the possibility that contracts might be granted for overlapping sections, leaving the government to pay multiple times for fixing that part.

We want a program that will examine the contracts and will tell us how many feet of highway have been included in more than one contract. Create a class RoadWork that contains a method fraudFeet that takes int[] start and int[] end as input and returns the number of feet of highway that are included in more than one contract. Corresponding elements of start and end give the starting and ending location of a contract.

 

Definition

    
Class:RoadWork
Method:fraudFeet
Parameters:int[], int[]
Returns:int
Method signature:int fraudFeet(int[] start, int[] end)
(be sure your method is public)
    
 

Notes

-Keep in mind that the highways can potentially be very long (2,000,000,000 feet) and that your program must run in 8 seconds, and use less than 64 MB of memory.
 

Constraints

-start contains between 1 and 50 elements inclusive
-end contains the same number of elements as start
-each element of end is greater than the corresponding element of start
-each element of start and end is between 0 and 2,000,000,000 inclusive
 

Examples

0)
    
{50,50,50}
{58,58,60}
Returns: 8
All three contracts cover the section from 50 to 58
1)
    
{171234,12,20,30}
{171236,20,30,40}
Returns: 0
2)
    
{12,32,92}
{991,161,1093}
Returns: 959
32 to 92 is covered by the first 2 contracts, 92 to 161 is covered by all the contracts, and 161 to 991 is covered by the first and last contract. The answer is (92-32) + (161-92) + (991-161)

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4462&pm=1307

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Math, Sorting