Question

a) Devise a greedy algorithm that determines the fewest lecture halls needed to accommodate n talks given the starting and ending time for each talk.

Short answer

It is proved that the greedy algorithm does not always determine the fewest lecture halls needed to accommodate n talks given the starting and ending time for each talk.

Step-by-step solution

Step 1:

We know that an algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.

So, the one way to process is the order the talks by starting time. Then, we number the lecture halls and so on.

Now, we will see the greedy algorithm for scheduling talks:

Step 2:

$e_1\le e_2\le \dots \le e_n$Procedure schedule

$\left(s_1\le s_2\le \dots .s_n\text{: start times of talks, (}{e}_1\le e_2\le \dots \le e_n\right.\text{: ending times of talks)}$

Sorts talk by finish time and reorder so that

For j : = 1

For i := 1 to N ( N is the number of lecture halls)

If talk j is compatible with i then we assign talk j to lecture hall i .

Therefore, it is proved that the greedy algorithm does not always determine the fewest lecture halls needed to accommodate n talks given the starting and ending time for each talk.