Greedy algorithms

In the IntervalCover problem, the input is a set of n points on the line 0 <= p1 < p2 < < pn < M , and the valid solution is the minimum number k of unit intervals [x1 , x1 + 1] ,, [xk , xk + 1] required to cover all n points. (A point pi is covered by the interval [ xj , xj + 1] if xj <= pi <= xj + 1.

a) Show that the greedy algorithm that at each step selects an interval that covers the largest number of still-uncovered points does not solve the problem.

b) Describe a greedy algorithm that solves the IntervalCover problem.Prove that your algorithm always returns a valid solution