In the IntervalCover problem, the input is a set of n points on the line , and the valid solution is the minimum number k of unit intervals required to cover all n points. (A point is covered by the interval if

(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.