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
{50,50,50}{58,58,60}Returns: 8
All three contracts cover the section from 50 to 58{171234,12,20,30}{171236,20,30,40}Returns: 0
{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)
Back to all problems