Chapter 4

This section deals with the Interval Scheduling problem, and implements a greedy algorithm to solve it.

The interval scheduling problem deals with scheduling job requests. We want to schedule as many jobs as possible, but to do so we need to pick only jobs that do not overlap. Each given job has a beginning and end time.

The solution to this problem is deceptively simple: we start with the request that has the earliest end time possible. Then, we delete all requests that conflict with this accepted request. Then we choose the job that has the next earliest end time. We repeat this algorithm until there are not more requests to either delete or accept, and the accepted jobs are the optimal set. It is important to distinguish that this algorithm works because all jobs have the same value, so our only concern is taking on the highest number of jobs.

This section then goes on to prove that this algorithm is optimal. First, it proves by induction that no two accepted jobs overlap (f(i_r) =< (f(j_r)). Then, it proves by contradiction that the set the greedy algorithm returns is optimal by contradiction. With these two points proven, we can now say that the solution returned is correct and optimal. This algorithm runs in O(n log n).

This section also describes the Interval Partitioning problem, which is similar to the Interval Scheduling problem. This algorithm mostly operates under the same processes described above, except when two jobs overlap, the conflicting jobs are put onto different “resources” (think scheduling lectures in two different classrooms). Therefore, the optimal number of “resources” needed to schedule the jobs is equal to the maximum number of overlapping jobs at any one point in time.