StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q59E

Expert-verifiedFound in: Page 204

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.

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:

${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.

94% of StudySmarter users get better grades.

Sign up for free