We shall say that a subset of requests is compatible if no two of them overlap in time, and the goal is to accept as large a compatible set subset as possible. Compatible sets of maximum size will be called optimal. Designing a Greedy Algorithm. We shall use a simple rule to select a first request i. Once i is accepted we reject all other requests that re not compatible with it. Then accept the next request compatible with i, and then reject all incompatible with i2, we keep doing this until we run out of requests. What rule should we use? Possible natural rules are: starts earlier, smallest interval of time, and many other natural rules can be used. But our point is to be able to select the interval with the fewest “conflicts”. As we shall examine all possible rules, the greedy rule that will give an optimal solution is that that accepts first the request that finishes first. Algorithm on Page 118. When analyzing the algorithm, we need to show that the solution we've got is optimal. If O is an optimal set of intervals(there can be many optimal solutions), then we have to check if |A| = |O| where A is the solution set. If all elements of O are in A, then we have an optimal solution. Since we used a greedy algorithm to solve our problem, the proof that we got an optimal solution is finding a way to show that our greedy algorithm “stays ahead” of this solution O, and that it is doing better in a step-by-step fashion. Let i1,i2,…,ik be the set of requests in A, and |A|=k. Also, let j1,j2,…,jm be the set of requests in O. We have to show that k=m. To show that the greedy algorithm stays ahead, we need to show that the finish time of job in A is either less or equal to the finish time of the job in O at the same index. Since this is true, every request compatible with O should be compatible with A, detailed proof on Page 120-121. The running time of this algorithm is O(nlogn) time, but we can make it perform better by implementing the greedy algorithm analyzed above in one pass through the intervals, spending constant time per interval, thus spending O(n) time. In practical settings, such a problems could arise thus causing further complications. Some of these are what if the scheduler needs to make decisions about accepting or rejecting certain requests before knowing about the full set of requests??? What if our goal was to maximize income depending on their interval lengths??? Another Scheduling problem that we are going to discuss is one where we have identical resources available and we wish to schedule all the requests using as few resources as possible. We refer to this problem as the Interval Partitioning Problem. An example would be class scheduling in as few classrooms as possible. Suppose we define the depth of a set of intervals to be the maximum number that pass over any single point on the time-line, then In any instance of Interval Partitioning, the number of resources needed is at least the depth of the set of the intervals. Proof is on Page 123. The algorithm we use for this is a simple one-pass greedy startegy that orders intervals by their starting times. We go through the intervals in this order, and try to assign to each interval we encounter a label that hasn't already been assigned to any previous interval that overlaps it. Algorithm detail on Page 124. We claim that using this greedy algorithm, every interval will be assigned a label, and no two overlapping intervals will receive the same label.Proof on page 125. Summing up, the greedy algorithm above schedules every interval on a resource, using a number of resources equal to the depth of the set of intervals, and this is the optimal number of resources needed. Is there a general way of defining a greedy algorithm that is applicable to any problem given any constraints? No. The greedy algorithm itself is determined depending on the constraints.

This section was a bit longer than the prior ones but it was readable. I would give it a scale of 8/10.