A busy professor has to complete N projects. Each project i has a deadline di and the time it takes the professor to complete it is Ti. The professor can work on only one project at a time and must complete it before moving on to a new project. For a given order of completion of the projects, denote by ti the time of completion of project i, i.e
The professor wants to order the projects so as to minimize the maximum tardiness, given by
Use an interchange argument (cf. Exercise 10.24) to show that it is optimal to complete the projects in the order of their deadlines (do the project with the closest deadline first).