Describe an efficient algorithm that given a set x1 x2 xn o

Describe an efficient algorithm that, given a set {x_1, x_2, ..., x_n} of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given points. Argue that your algorithm is correct.

Solution

Answer:

The array of n points on the real line is A[1..n]: Points A[1] < A[2] < … < A[n]

The array of intervals B[1..m]:   Intervals [B[j], B[j] +1]

Algorithm smallest-set (n)

Step1 : m := 1;

Step 2 : B[1]:= A[1];

Step 3 : for j := 1 to n do

Step 4 : if (A[j] > B[m] +1)

Step 5 : m: = m+1; // Adds a new interval

Step 6 : B[m]:= A[j];

else

Step 7 : A[j] is in [B[m], B[m] +1]

Step 8 : return m;

Proof of the algorithm:   

Theorem:

smallest-set returns the minimal number of unit intervals that cover

                                  A[1], A[2], …, A[n].

Lemma: None of the intervals obtained by smallest-set can move right by any distance, otherwise some points won’t be covered.

Proof: Induction on m

Base case: m = 1 and B[1] = A[1]. If [B[1], B[1]+1] moves right, then A[1] cannot be covered.

Inductive hypothesis: Suppose none of the first m intervals can move right. When A[j] > B[m] +1, the last interval [B[m], B[m]+1] cannot cover A[j] (and it cannot move right). So need a new interval and let it be [A[j], A[j] +1], which cannot move right; otherwise A[j] cannot be covered.