This is an old revision of the document!

Chapter 4

4.1 Interval Scheduling

A greedy algorithm is one that involves no backtracking or other global optimization–it builds the solution by a simple metric and does not rethink what it has already done. Interval scheduling is easily solved by adding the first to end of the tasks that do not conflict with any other until there are no more such. It can be proven optimal by “greedy stays ahead”–its ith task must finish no later than the ith task of any other valid solution by a simple induction based on the selection criterion. A related algorithm can schedule all tasks (to an arbitrary number of processors)–take the tasks by start time, assigning each to an available processor and adding another when none are available. This can be proven optimal very directly–it will always produce a solution using the same number of processors as the input is deep, which is obviously the least possible. As before, running time is O(n log n), coming from the initial sort.
No insights.
No questions.
No other complaints.

A related problem is the scheduling of tasks of fixed duration (but not time) to minimize maximum lateness. This can be solved by a very simple greedy algorithm, simply sorting the tasks by deadline and then scheduling them in that order with no gaps. This can be shown optimal by exchange; if an optimal solution has an inversion, where an early job has a later deadline than a later job, reversing the inversion will reduce the maximum lateness if the later job (by the first schedule) was the latest, or else not effect the maximum lateness; therefore, an optimal solution can be transformed into the greedy solution without increasing maximum lateness. Likewise, removing idle time will weakly decrease maximum lateness. Therefore, the greedy solution is optimal.
I was glad to see formal treatment of the possibility of jobs with identical deadlines (4.8)–I do not recall such a clause in the proof in class, and while not a weakness in the algorithm, it does seem a weakness in the proof. At the same time, I prefer the proof by contradiction (let S be the schedule with the fewest inversions; if S has any inversions, there is an optimal schedule with fewer inversions) to their proof by induction, that a series of exchanges can transform an arbitrary optimal schedule into an inversionless optimal schedule.
No questions.
The complaint against the induction in the proof aside, fairly well done.