Chapter 4

This section discusses the Greedy Stays Ahead algorithm. It focuses on maximizing the number of compatible intervals that can be scheduled. It refers to the maximal compatible set as optimal. In designing possible algorithms, it discusses the natural ways we could go about picking a first interval. One not optimal solution is to simply pick the earliest interval, but this does not work. The next idea is picking the shortest interval, but this can not work as well. Another idea that does not pan out is picking the interval with the fewest conflicts. The rule that does work is picking the first interval to end, or the interval with the first end time.

Initially let R be the set of all requests, and let A be empty

While R is not yet empty

→Choose a request i in R that has the smallest finishing time

→Add request i to A

→Delete all requests from R that are not compatible with request i

EndWhile

Return the set A as the set of accepted requests

This is the pseudocode for the algorithm. It can be shown to run in O(nlogn). Extensions of this problem include the problem where we do not know all intervals at the start. This is an online algorithm, which requires making decisions as time progresses. Additionally, we could modify this problem to change the weight, or reward, of certain intervals.

Another problem that is looked into with more depth is the scheduling all intervals problem, or the interval partitioning problem. This problem can be visualized as providing a class room for multiple lectures while using as few class rooms as possible.

Sort the intervals by their start times, breaking ties arbitrarily Sort intervals by starting time so that s1 ≤ s2 ≤ … ≤ sn d = 0 for j = 1 to n if (lecture j is compatible with some classroom k) schedule lecture j in classroom k else allocate a new classroom d + 1 schedule lecture j in classroom d + 1 d = d + 1

This algorithm runs in O(nlogn).

I honestly find these problems very interesting as the idea of solving these optimally with fairly straight forward, intuitive means in a good run time is cool, for lack of a better term. I enjoy learning about these types of problems. We did, however, already learn it in class, so the long reading kind of dragged on. I give this a 5/10.

This section's problem involves having a single resource and using the minimum amount to accomplish the set of tasks that consist of a time requirement and deadline.

The algorithm is as follows:

Order the jobs in order of their deadlines

Assume for simplicity of notation that dl…dn

Initially, f= s

Consider the jobs i=l ….. n in this order

→Assign job i to the time interval from s(i)=f to f(i)=f+ti

→Let f = f + ti

End

Return the set of scheduled intervals [s(i),f(i)] for f= 1 ….. n

This algorithm runs in O(nlogn). An extension of this problem would be allowing for events to have a “release” time or earliest possible start time.

This section is similar to the first, and my thoughts on it mirror that of 4.1. As such, it once again gets a 5/10.