Describe an efficient algorithm that, given a set {x1, x2,...,xn} of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given points. (A unit length interval just means any closed interval with length 1. I. e., an interval [a, b] where b − a = 1.)

a. Briefly describe a greedy algorithm for the unit length interval problem.

b. State and prove a "swapping lemma" for your greedy algorithm.

c. Write a proof that uses your swapping lemma to show that your greedy algorithm does indeed produce a set of intervals that contain all of the points {x1, x2,...,xn} with the fewest number of intervals.

Check the explanation

Explanation:

A. Below is the simplest Greedy algorithm :-

1. Sort all the points x1, x2,,xn in ascending order on real line and store it in set X which is set of uncovered points .

2. Remove the leftmost point say point with coordinate x from set X.

3. Select interval {x,x+1} in solution set of unit length interval.

4. Remove all points from set X covered by interval {x,x+1}.

5. Repeat step 2 to 4 for remaining uncovered points in set X.

b. Swapping lemma :- There cannot be any solution which can minimize further the set of intervals as selected by Greedy algorithm by swapping above set of selected intervals with any other interval.

Proof :- Since the leftmost point say x has to be covered by some interval, Greedy algorithm is selecting rightmost possible interval to cover the point x by selecting interval {x,x+1}. So to cover point x, swapping interval with any other interval {y,y+1} with y<x will not be better than interval {x,x+1} .

Now let Greedy algorithm optimally covers set of m leftmost points in set X. Then at (m+1)th point, if this point is covered by already selected interval then definitely Greedy algorithm gives optimal solution even for leftmost m+1 points and if (m+1)th point need an extra interval then no optimal algorithm could have covered all these m+1 points without taking an extra interval because Greedy algorithm try to cover m points in minimum possible interval and the rightmost interval in Greedy algorithm has maximum possible rightward extension . Hence Greedy algorithm works optimally even for set of m+1 points.

Hence by induction, we proved swapping lemma for this Greedy algorithm.

c. Claim :- The intervals selected by above Greedy algorithm is minimum possible interval.

Proof :- We have just shown by swapping lemma that by swapping set of intervals selected by Greedy algorithm does not provide solution with further less number of intervals. So clearly selecting interval with starting point equal to leftmost uncovered point is always a part of some optimal solution and since our Greedy algorithm is selecting interval based on leftmost uncovered point as the starting point, hence by swapping lemma, the solution returned by this Greedy algorithm is always an optimal solution.