Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 7

(a)

Let G be the greedy selection of tasks and let O be the optimal selection. If G and O have the same number of tasks, then the greedy selection is also optimal. Assume that the greedy selection has fewer tasks than does the optimal selection. Arrange the tasks in each selection in increasing order of finish time. Now compare the two selections from left to right and find the least i such that the ith tasks in the greedy and optimal selections are different. Such an i must exist as otherwise the greedy selection agrees fully with the left part of the optimal selection. This is not possible because the greedy algorithm would have selected at least one more task (since the optimal has a task with start time > largest finish time of any task in the greedy selection).

From the way the greedy algorithm works, we see that the finish time of task i of the greedy selection is <= that of task i of the optimal selection. Task i of the greedy selection is not one of the tasks selected by he optimal algorithm. Replace task i of the optimal selection with task i of the greedy selection. The result is a new optimal selection which agrees with the greedy selection at least up to the ith tasks.

By repeating this replacement step several times (bounded by the total number of tasks), we transform the original optimal solution into a new optimal solution in which the first |G| tasks (|G| is the number of tasks in G) are the tasks in the greedy solution. From the way the greedy algorithm works, we know that it is not possible to add any tasks with larger finish time to the selection. Therefore, the optimal solution cannot contain any additional tasks. So the greedy selection is of the same size as the optimal selection; it is, therefore, an optimal selection.

(b)

If we choose to use the hint, we can begin by initializing a min heap with the tasks and then extract the tasks from the min heap in nondecreasing order of finish time. When a task is extracted from the min heap, we see if it is possible to add it to the set of already selected tasks. An alternative strategy is to first sort the tasks into nondecreasing order of finish time and then examine them one at a time in this order.