Lect 22: Optimal Algorithm for Interval Scheduling

In today’s lecture we proved that the greedy algorithm that processes interval according to their finish time gives an optimal solution to the Interval Scheduling problem. The slides have been posted.

On Monday, we will quickly go over the run time analysis of the algorithm (Sec 4.1 in the book) and then move on to another scheduling problem where one wants to minimize the maximum lateness (Sec 4.2 in the book).

Here are the links to the student blog posts for this lecture:

• Alex Janikowski
• Nicholas McClure