Show that a greedy algorithm that schedules talks in a lecture hall, as described in Example 7. by selecting at each step the talk that overlaps the fewest other talks, does not always produce an optimal schedule.

Solution :Step 1:In this problem, we have to show that the greedy algorithm that schedules talks in a lecture hall, if selecting at each step the talk that overlaps the fewest other talks, does not always produce an optimal schedule.Step 2:Greedy Algorithm: The greedy approach works for a number of optimization problems, including some of the most fundamental optimization problems in computer science. Thus this is an important algorithm design technique to understand. Even when greedy algorithms do not produce the optimal solution, they often provide fast heuristics(nonoptimal solution strategies) and are often used in finding good approximations. Greedy Algorithm for selection problem: Now the Lecture -Hall Assignment(s ,f) n= length [s] For i = 1 to n Do HALL [i] = NIL k= 1 While (Not empty (s)) do HALL [k] = GREEDY -ACTIVITY-SELECTOR(s,t,n) k = k+1 Return HALL