Algorithims. greedy algorithim

1. You are given a set X = {z? ,T2, . . . ,Zn} of points on the real line. Your task is to design a greedy algorithm that finds a smallest set of intervals, each of length 2, that contains all the given points. Example: Suppose that X-1.5, 2.0, 2.1,5.7,8.8,9.1,10.21. Then the three intervals [1.5,3.5], [4, 6], and [8.7,10.7] are length-2 intervals such that every x E X is contained in one of the intervals. Note that 3 is the minimum possible number of intervals because points 1.5, 5.7, and 8.8 are far enough from each other that they have to be covered by 3 distinct intervals. Also, note that my solution is not unique for example, I can shift the middle interval [4, 6 to the right, say to [5.7,7.7, without disturbing the other intervals, and we would still have an optimal solution. (a) Suppose that elements of X are presented in increasing order. Describe (using pseu- docode) a greedy algorithm, running in O(n) time, for this problem. (b) Using the approach that we used for the proof of correctness of the Interval Scheduling greedy algorithm prove that your algorithm indeed produces an optimal solution. Your proof needs to be clear and precise, in addition to being correct