Describe an efficient algorithm that, given a set {x1, } 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, } with the fewest number of intervals.

note: you must show that no smaller set of intervals exists that contain all of the points. do not appeal to any general principles. you must incorporate your swapping lemma above in the proof.

argue that your algorithm is correct.