4.1: Interval Scheduling: The Greedy Algorithm Stays Ahead

For this problem, we'll say that a subset of the requests is compatible if no two of them overlap in time. Our goal is to accept as large a compatible subset as possible. Compatible sets of maximum size will be called optimal.

Designing an Algorithm

We should order the requests by earliest finish time, this is explained on p.117. Here is the algorithm for Interval Scheduling

Initially let R be the set of all requests, and let A be empty
While R is not empty
  Choose a request i within R that has the smallest finishing time
  Add request i to A
  Delete all requests from R that are not compatible with i
  
Return the set A as the set of accepted requests

Analysis

Our intuition for the greedy method came from wanting our resource to become free again as soon as possible after satisfying the first request. This greedy rule guarantees that f(i(1)) ⇐ f(j(1)). This is the sense in which we want to show that our greedy rule “stays ahead.”

Running time: O(nlogn) - this is because it takes O(nlogn) to sort, and the rest of the algorithm runs O(n) → O(nlogn) + O(n) = O(nlogn).

Scheduling All Intervals

There is a related problem in which we wish to schedule all the requests using as few resources as possible. This is called the Interval Partitioning problem. We find that in any instance of Interval Partitioning, the number of resources needed is at least the depth of the set of intervals.

Depth → the maximum number of requests that pass over any single point in time.

Here is the algorithm for interval partitioning:

Sort the intervals by their start times, breaking ties arbitrarily
Let i(1), i(2),....i(n) denote the intervals in this order
For j = 1,2,3,...,n
  For each interval I(i) that precedes I(j) in sorted order and overlaps it
    Exclude the label of I(i) from consideration from I(j)
  If there is any label from {1,2,...d} that has not been excluded 
    Assign a nonexcluded label to I(j)
  Else
    Leave I(j) unlabeled

This greedy algorithm above schedules every interval on a resource, using a number of resources equal to the depth of the set of intervals. This is the optimal number of resources needed.

This section was really helpful in understanding the intuition as to why start/finish times are chosen first for different problems. 9/10.