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.