for this question proof only used the Greedy Algorithms (scheduling classes).

Suppose that we have a set of m 1 points, x1 < x2 < < xm, on the real number line. We want to find a smallest possible set of unit-length closed intervals that covers all of the points.

For example, if the points are {1.3, 2.1, 3.7, 4.4, 4.6, 6.8, 8.5, 8.8, 9.3}, then one optimal solution would include the four intervals [1.3, 2.3], [3.7, 4.7], [6.8, 7.8], [8.5, 9.5]. Note that every point in the list is included in one of these four intervals, and it is not possible to find a set of three intervals that works.

Consider the following greedy algorithm to solve this problem:

Add the interval [x1, x1 + 1.0] to the list

for i from 2 to m

if xi is not covered by the most recent interval added then

add the interval [xi , xi + 1.0] to the list

Let G1, G2, , Gp be the set of intervals chosen by this greedy algorithm for a set of m points. Prove that this is an optimal solution.

Use a proof by contradiction. Suppose that G1, G2, , Gp is not optimal, and let O1, O2, , Oq (with q < p, and with the intervals sorted in increasing order) be some optimal solution.

Within your proof, use a proof by induction to show the following: For all n 1, the total number of points covered by the intervals G1, , Gn must be greater than or equal to the total number of points covered by the intervals O1, , On.

Use this to help you to contradict the assumption that q < p