• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q59E

Expert-verified Found in: Page 204 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # 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.

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.

See the 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}\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. ### Want to see more solutions like these? 