Solution Found!
Find the complexity of the greedy algorithm for scheduling
Chapter 3, Problem 38E(choose chapter or problem)
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).
Questions & Answers
QUESTION:
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).
ANSWER:
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).