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.