**__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.