Problem 38E

Find the complexity of the greedy algorithm for scheduling the most talks by adding at each step the talk with the earliest end time compatible with those already scheduled (Algorithm 7 in Section 3.1). Assume that the talks are not already sorted by earliest end time and assume that the worst-case time complexity of sorting is O(n log n).

Solution:

Step 1:

In this problem,we have to find the complexity of the greedy algorithm for scheduling the most talks by adding at each step the talk with the earliest end time compatible with those already scheduled and we also assume that the talks are not already sorted by earliest end time and assume that the worst-case time complexity of sorting is O(n log n).