Greedy algorithms essentially use a localized decision making process to yield a globally optimal solution. Fortunately, the ability of a greedy algorithm to solve a nontrivial usually reveals a great deal about the structure and nature of the problem itself. In the first two sections of the chapter we will work through two example problems to illustrate two typical methods of proving the greedy algorithm indeed yields an optimal solution:

1. greedy stays ahead (and structural)
2. exchange argument.

The Interval Scheduling Problem consists of a set of n requests for use of a single resource, each i^th request corresponding to an interval of time starting at s(i) and ending at t(i). Essentially, we want to get the maximum number of “jobs” scheduled where none of them overlap. The efficient method of this is a greedy algorithm.

In this particular case, the book (and in class, we) discussed that the greedy rule should be based on accepting the valid (meaning does not overlap with the jobs already set) job which finishes first–the job which minimizes f(i). This maximizes the open time after adding a single job. So, we let R denote the list of jobs we haven't processed yet, and A be the set of jobs we've accepted in building our final schedule. The algorithm (as discussed in class, because the book's version is far too removed from actual implementation) is thus as follows:

• Sort jobs in R by finish times so that f(1)=<f(2)=<…=<f(n)
• A = {}
• for j=1 to n
  • if job j compatible with A
    • add j to A
• return A

Firstly, its clear that A is indeed a compatible set of jobs. Next, we must show that A is optimal. Suppose that O is an optimal set of intervals, thus we must show that |A|=|O|. Let i_r and j_r be the r^th job in each final set.

Note then that our greedy rule guarantees that f(i₁)=<f(j₁), because the greedy rule automatically pick the one with the lowest end time. Then, through induction we can prove that

• for all indices r=<k we have that f(i_r)=<f(j_r).

Then, if A is not optimal, then O would have to have more jobs. But, we know that up to equal number of jobs, the end time of the greedy solution's last job is less than the end time of that same numbered job in the optimal, meaning that the additional one in the optimal would have been grabbed by the greedy algorithm too–a contradiction.

So, we know A returned by the greedy algorithm is indeed optimal.

Sorting the jobs takes O(n logn) time as we know. Then, the comparisons and adding each take simply constant time because we can maintain the value of the end time of G and simply compare the start time of the next jobs. So, the for loop is O(n), and our whole algorithm runs in O(n logn).

A variation on the problem we just did is the interval partitioning problem. The easiest way to think of this is a set of class lectures that each occur at specific time intervals, and we want an algorithm to return a schedule that minimizes the number of classrooms required.

We define the depth of the set of intervals to be the maximum number that overlap at a given time. Clearly, the number of classrooms needed is at least the depth of the set. We proceed to give an algorithm which schedules all lectures in a number of classrooms equal to the depth.

Suppose we are given a set of intervals. Let d be the depth of the set. We will work to assign each interval (class lecture) a label from 1 to d, which we can interpret as the classroom designated for that lecture. The following algorithm begins by sorting the intervals according to start times, and then we assign the first a label (1), and then iterate through the sorted intervals, adding them to the same classroom if they fit, and if not, adding them to the next highest classroom label. The algorithm is as follows:

• Sort intervals by start times so that s(1)=<s(2)=<…=<s(n)
• d = 0 (number of allocated classrooms)
• 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

We see that every interval will be assigned a label and no two overlapping intervals will receive same label. We know we will never reach a point where all labels are currently in use due to the structural argument that the depth is indeed maximum. So, we will never be triggered to use a depth+1 level classroom. Hence, our output schedule is indeed optimal.

We know that this runs O(n logn).

In this problem, we are given a set of tasks, each which takes a set time to complete (t(j)), and has a set deadline (d(j)). We proceed to give an algorithm which will minimize the maximum lateness among all the tasks (again assuming none can overlap):

• Sort n jobs by deadline so that d(1)=<d(2)=<…=<d(n)
• t = 0
• for j=1 to n
  • assign job j to interval [t, t+t(j)]
  • s(j)=t
  • f(j)=t+t(j)
  • t=t+t(j)
• output intervals [s(j),f(j)]

We can make a number of observations. First, there is of course an optimal schedule with no idle time (time in which no job is being done). Defining an inversion to be jobs i and j such that i is scheduled before j but d(j)<d(i), we note that our algorithm automatically produces a schedule without inversions. Additionally, we know that all schedules with no inversions and no idle time have the same maximum lateness–because it then would only depend on swapping of adjacent jobs that have the same deadline.

Now, consider an optimal schedule O, with no idle time. We know that if O has an inversion, then there is a pair of jobs i and j such that j is immediately after i and has d(j)<d(i). This means that if there is an inversion somewhere, there must be an adjacent inversion somewhere.

Suppose O has at least one inversion, and suppose i and j are an adjacent inversion as mentioned above. Then we know that upon swapping them, no new inversion is created, but we eliminate one. So we swap them and get a schedule with one less inversion.

Now, a more nuanced proof based on inequalities illustrates that swapping any given inverted pair will not increase maximum lateness.

Therefore, we can continue the process of doing so from any arbitrary O, and end up at the schedule (or an equivalent, if there are equal end times) produced by our greedy algorithm