Use the Greedy algorithms

In the Interval Cover problem, the input is a set of n points on the line 0 p₁ < p₂ < < p_n M, and the valid solution is the minimum number k of unit intervals [x₁, x₁ + 1], . . . , [x_k, x_k + 1] required to cover all n points. (A point pi is covered by the interval [x_j , x_j+ 1] if x_j p_i x_j + 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.