Interval Scheduling Problem
Schedule the jobs so that the number of jobs scheduled is maximized and jobs do
J: The set of jobs
i: The i job
s: The start time of the i job
fi The finish time of the i job
Ordering: Sort the jobs by increasing finish time.
3 ,6j 1 j7, j4, 2 ,5j , j
Scheduling: Schedule each job if there are no conflicts.
j3, 7 ,5j
Proof if the algorithm is best - Proof by Contradiction:
Play Devil’s Advocate
Assume our solution is not the best. This means there is a better solution
Show that our algorithm’s solution is as good as B by making B equivalent