====== 4.1. Interval Scheduling: The Greedy Algorithm Stays Ahead ======

The Greedy Algorithm stays ahead means that if we measure the greedy algorithm's progress in a step-by-step fashion, we see that it does better than any other algorithm. Thus it produces an optimal solution. For the Interval Scheduling Problem, we have a set of requests {1,2,3,...,n} where the i<sup>th</sup> request corresponds to an interval of time starting at S(//i//) and finishing at //f(i)//. A subset of requests is //compatible// if no two of them overlap in time,and our goal is to accept as large a compatible subset as possible. Compatible subsets of maximum size are called //optimal//.\\
\\
==== Designing a Greedy Algorithm ====

--> The basic idea when designing a greedy algorithm for the interval scheduling problem is to select a first request //i//<sub>1</sub>. Once the first request is selected, all of the requests not compatible with it are rejected. We then select the next request //i//<sub>2</sub> to be accepted,and eliminate all of the requests not compatible with it. We continue in this way until there are no more requests.\\
\\
-->Thus the biggest issue is to find a simple way of selecting requests.\\
\\
--> To select the first request, we examine a number of options,and decide which greedy rule can give us the optimal solution. It turns out that one of the best choices would be to select a request with the fewest conflicts possible: the request with the fewest number of non compatible requests. When we can find a counterexample to our best choice greedy rule, we can still use another greedy rule to find an optimal solution. In this case, we choose the greedy rule that gives us the next big subset with the fewest number of non compatible requests \\
\\

=== Algorithm ===

>>>>>>>Let R be a set of all requests, and let A be the set of accepted requests
>>>>>>>Initially, let A be empty
>>>>>>>While R is not 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//
>>>>>>>End While
>>>>>>>Return the set A as the set of accepted requests

===Algorithm Analysis And implementation===


  * The set A returned is that of compatible requests and it is optimal.
  * For all indices r ≤ k, we have f(//i//<sub>r</sub>) ≤ f(//j//<sub>r</sub>), f(//j//<sub>r</sub>) being the finishing time of the request in the optimal solution corresponding to the request f(//i//<sub>r</sub>) in A
\\
==Implementation ==

-->Our goal: A O(nlogn)running time

>>>>>>>>> First sort the n requests in order of finishing time and label them in this order:f(//i//) ≤ f(//j//) if i ≤  j. Sorting takes O(nlogn) time)
>>>>>>>>>We then construct an array S[1,...,n] where S[//i//] contains the value S(//i//). This takes O(n) time.
>>>>>>>>>>>>>>>>>Now we select requests in order of increasing f(//i//). We always select the first interval.
>>>>>>>>>>>>>>>>>Then iterate through the interval in order until S(//j//) ≥ f(1). We then select this interval S(//j//).
>>>>>>>>>>>>>>>>>In this way, we spend O(1) time per each interval and implement our greedy rule in a single pass through the intervals. This part of the algorithm takes O(n) time.\\
\\
=== Extensions of the Interval Scheduling Problem ===

  * For all scheduling problems, all of the requests are not known in advance. In case all of the requests are not known in advance, the greedy algorithm must take decisions as time goes on.
  * The solution given here assumes all of the requests are of equal value. However, they may have different values associated with them, such as in the case of the Weighted Interval Scheduling Problem.
\\
=== A Related Problem: Scheduling all of Intervals ===

  * With this problem,we have many identical resources available and we wish to schedule all of the requests using as few resources as possible.
  * The goal here is to partition all intervals across multiple resources: Thus the problem is called the **Interval Partitioning Problem**.
  * The //depth// of a set of intervals is the maximum number of intervals that pass over any single point on the time-line
  * The number of of resources needed is always at least the depth of the set of intervals.
==Algorithm for the Interval Partitioning Problem ==

>>>>>>>>>Sort the intervals by their start times,breaking ties arbitrarily
>>>>>>>>>Let I<sub>1</sub>,I<sub>2</sub>,...I<sub>n</sub> be the intervals in that order
>>>>>>>>>For j = 1,2,3,...n:
>>>>>>>>>>>>>>>>>For each interval I<sub>i</sub> that precedes I<sub>j</sub> in sorted order and overlaps it:
>>>>>>>>>>>>>>>>>>>>>>>>>>>Exclude the label I<sub>i</sub> from considerations for I<sub>j</sub>
>>>>>>>>>>>>>>>>>End For
>>>>>>>>>>>>>>>>>If there is any label from {1,2,...d} that has not been excluded:
>>>>>>>>>>>>>>>>>>>>>>>>>>>Assign a non excluded label to I<sub>j</sub>
>>>>>>>>>>>>>>>>>else:
>>>>>>>>>>>>>>>>>>>>>>>>>>>Leave I<sub>j</sub> unlabeled
>>>>>>>>>>>>>>>>>End if
>>>>>>>>>>End For

--> With this algorithm, every interval is assigned a label and no two overlapping intervals receive the same label.\\
\\
--> This algorithm also schedules every interval on a resource using a number of resources equal to the depth of the set of intervals.\\
\\
After writing this section,I realized how tricky,yet simple, designing a greedy algorithm. As it was an introduction to greedy algorithm, one reading wasn't really enough for this section to make sense. But after rereading it, it now make senses.\\
\\
On our usual rating scale, I give this section an 8/10.