TopCoder problem "PipePatcher" used in TCHS07 Delta 2 (Division I Level Two)



Problem Statement

    

You are installing water pipes made by a company with poor quality control. In a single piece of pipe, you have found several leaks that should be fixed. The leaks are all aligned on top of the pipe, and each leak is an integer number of inches from the left end of the pipe. You have an infinite supply of L-inch long pieces of adhesive tape. Each leak must be covered by at least one layer of tape. To prevent the leaks from growing, you must always leave at least 0.5 inches of tape on each side of a leak. The leaks have negligible length, so a single leak can be covered by a 1-inch piece of tape.

You are given the positions of all the leaks in the int[] leaks. The i-th element is the distance of the i-th leak from the left end of the pipe. Return the minimum number of pieces of adhesive tape needed to fix them all.

 

Definition

    
Class:PipePatcher
Method:patches
Parameters:int, int[]
Returns:int
Method signature:int patches(int L, int[] leaks)
(be sure your method is public)
    
 

Constraints

-leaks will contain between 1 and 50 elements, inclusive.
-Each element of leaks will be between 1 and 1000, inclusive.
-All elements of leaks will be distinct.
-L will be between 1 and 1000, inclusive.
 

Examples

0)
    
2
{1,2,100,101}
Returns: 2
A 2-inch piece of tape can fix two leaks that are one inch apart, so two pieces are enough in this case.
1)
    
3
{1,2,3,4}
Returns: 2
There are several ways to cover all the leaks using two pieces of 3-inch tape, but it cannot be done with less than two pieces.
2)
    
1
{3,2,1}
Returns: 3
With the smallest tape size only one leak can be covered with each one.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10714&pm=7534

Writer:

ged

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy