Chapter 4: Greedy Algorithms

In the interval scheduling problem, we considered a set of requests {1, 2, …, n} where the i^th request corresponds to an interval of time beginning at s(i) and finishing at f(i). A subset of the requests is compatible if no two of them overlap in time. We would like to maximize the compatible subset, which would be the optimal subset. A greedy algorithm for interval scheduling could be designed as follows:

  Initially let R be the set of requests and let A be empty
  While R is not empty
      Choose a request i ∈ 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 set A as the set of accepted requests

We want to prove that this solution is optimal, and we know that A is a compatible set of requests. To prove that greedy “stays ahead” we will set O to be the optimal set of intervals, and we want to show that A contains the same number of intervals as O. If we let i₁, …, i_k be the set of requests in A in the order they were added to A and j₁, …, j_m be the set of requests in O in the order they were added to O, then we want to prove that k = m. Using induction, we can prove that for all indices r ≤ k, f(i_r) ≤ f(j_r). Because of this, we know that for each r, the r^th interval finishes at least at the same time, if not earlier, than the r^th interval in O. The running time of this algorithm is O(nlogn).

There are many variations and extensions of the Interval Scheduling Problem, for example the Interval Partitioning Problem, where there are many identical resources which we must schedule all the requests to use as few of as possible. The algorithm for this problem is seen here:

  Sort the intervals by start times, breaking ties arbitrarily
  Let I1, ..., In denote intervals in this order
  For j = 1, 2, 3, ..., n
      For each interval Ii that precedes Ij in sorted order and overlaps it
          Exclude the label of Ii from consideration for Ij
      Endfor
      If there is any label from {1, 2, 3, ..., d} that has not been excluded then
          Assign a nonexcluded label to Ij
      Else leave Ij unlabeled
  Endfor