This is an old revision of the document!
Table of Contents
Chapter 4 - Greedy Algorithms
Section 4.1 - Interval Scheduling: The Greedy Algorithm Stays Ahead
The section begins by bringing back a problem from earlier in the text: the Interval Scheduling Problem. In this problem, we are given a set of requests with start and finish times, and we are asked to find the largest subset of requests such that none of the times overlap. We want to devise a greedy algorithm to solve this problem.
The book walks through the different strategies we could use: ordering by start times, total time intervals, basing intervals on other intervals, and finally, finish times. It turns out that by ordering the requests by finish times, we have a greedy algorithm that matches the optimal solution.
The algorithm begins with a while loop on the set of all requests R. It says that while that set is nonempty, we choose the request with the smallest finishing time, we add that request to our set A (which will contain the solution), and then delete all requests from R that are not compatible with the request we just added to A. This algorithm is intuitive, and the book walks through the proof behind it well. Finally, the text diagnoses the runtime of the algorithm which is O(nlogn). Note that the runtime here is caused by ordering the finish times in sorted order, which we know takes O(nlogn) time.
Next, the book moves on to a similar problem. Here, we are given another set of requests, and we wish to schedule all of these requests using as few resources as possible. The book provides a good example to contextualize this using the idea that if we are given a set of class times, how many classrooms will we need to accommodate these class times. The text proves the intuitive fact that the number of resources needed is at least the depth of the set of intervals.
The algorithm follows similarly from the algorithm produced earlier in the section. First, we sort the intervals by their start times. As we progress through these sorted intervals j = 1,2,…,n, for any two intervals that are overlapping, we exclude the label from the preceding (earlier) interval I_i from consideration with the later interval I_j (in the same resource). And then if there is a label that has not been excluded during this call of the for loop, we assign a nonexcluded label to I_j. If there does not exist such a label, we leave I_j unlabeled.
The book does not diagnose the runtime of this algorithm. However, it does analyze the algorithm, ultimately concluding that the algorithm will schedule every interval on a resource, using a number of resources equal to to the depth, which was not as clear before reading the section carefully.
This section was long, and hard to follow at times. I would rate the readability at 5/10.
