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^th 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.

–> The basic idea when designing a greedy algorithm for the interval scheduling problem is to select a first request i₁. Once the first request is selected, all of the requests not compatible with it are rejected. We then select the next request i₂ 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

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

• The set A returned is that of compatible requests and it is optimal.
• For all indices r ≤ k, we have f(i_r) ≤ f(j_r), f(j_r) being the finishing time of the request in the optimal solution corresponding to the request f(i_r) in A

–>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.

• 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.

• 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.

Sort the intervals by their start times,breaking ties arbitrarily
Let I₁,I₂,…I_n be the intervals in that 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 I_i from considerations for I_j

End For
If there is any label from {1,2,…d} that has not been excluded:

Assign a non excluded label to I_j

else:

Leave I_j 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.