Chapter 4

Section 4.1 covers the introduction to greedy algorithms using the basic “staying ahead” mentality. There are two specific algorithms that are introduced in this section. The first is the interval scheduling algorithm which returns the optimal schedule of intervals from some given set of intervals. The algorithm works by finding the interval that has the earliest finishing time, removing all intervals that conflict with the chosen intervals, and then recursing through the remaining intervals until there are not left. The run-time of this algorithm is O(nlogn). The second algorithm schedules all intervals in an optimal fashion such that the number of resources used is no more than the depth of the intervals. The algorithm works by going through each interval and removing any other intervals that conflict with it. Then, after excluding all of the conflicts, the algorithm stitches together the remaining intervals together so that the fewest resources have to be used.

I give this chapter a 6 for readability since the proofs were sometimes hard to understand a 7 on the interesting scale.