Chapter 4: Greedy Algorithms

The Interval Scheduling Problem consists of a set of requests {1,2,…,n}, where the ith request corresponds to an interval of time starting at s(i) and finishing at f(i). When utilizing a greedy algorithm for the interval scheduling problem, we want to define a simple rule to select a first request. Once the first request is accepted, all other requests that are not compatible with the first request are rejected. Then, another compatible request is accepted, and again all of the other requests that are not compatible with it are rejected. This process repeats until you run out of the requests. The main challenge of this problem is deciding on what the rule should be for picking the next acceptable request. There are 4 main possibilities for choosing the order of the requests: choosing by earliest start time, choosing by shortest time required to complete the task, by the smallest number of coexisting requests during its time interval, and by earliest finish time. Choosing by earliest start time does not yield an optimal solution because if the earliest request i is for a very long interval, we may reject a lot of requests for shorter time intervals. Choosing by smallest interval of time does not yield an optimal solution, because it may cause the algorithm to choose a request of a smaller time interval by that results in only one request being chosen instead of two. Choosing by least number of incompatible requests also does not yield an optimal solution, because it may not choose the row with the most requests since they may conflict with lots of other rows. The correct way to choose the next request is by earliest finish time. We prove this by using the greedy stays ahead idea. The Greedy algorithm will always first choose the algorithm with the earliest finish time, so the possible start time of the next request will always be at least as early as the optimal solution. If the optimal solution has an extra request, the greedy algorithm will always add that request because its finish time will always be at least as early as the optimal solutions finish time. This algorithm will run in O(nlogn), since it will take nlogn time to sort the requests in order of finish time. Then selecting the requests will take place in constant time. Another related problem that can arise is trying to schedule all of the requests using as few resources as possible. 'In any instance of the Interval Partitioning Problem, the number of resources needed is at least the depth of the set of intervals'. The depth of a set of intervals is the maximum number that pass over any single point on the time-line. The algorithm used to solve this problem is very simple. You go sort the requests by finish time. Then you go one-by-one looking at the requests. For each request, you look at the current resources allocated. If the request can be added to a resource without conflict with another request, you add it to the resource, else you keep looking at other resources. If no such compatible resource is found, you must create a new resource and add the request to it. The algorithm will schedule every request on a resource using a number of resources equal to the depth of the set of intervals, which is the optimal number of resources needed.