Question

Use Algorithm 7 to schedule the largest number of talks in a lecture hall from a proposed set of talks, if the starting and ending times of the talks are 9:00 a.m. and 9:45 a.m.; 9:30 a.m. and 10:00 a.m.; 9:50 a.m. and 10:15 a.m.; 10:00 a.m. and 10:30 a.m.; 10:10 a.m. and 10:25 a.m.; 10:30 a.m. and 10:55 a.m.; 10:15 a.m. and 10:45 a.m.; 10:30 a.m. and 11:00 a.m.; 10:45 a.m. and 11:30 a.m.; 10:55 a.m. and 11:25 a.m.; 11:00 a.m. and 11:15 a.m.

Answer 1

Answer:

If we arrange the talks from the lowest starting time to the highest ending time we get total of 11 talks.

using algorithm 7 we get answer   (1) - (3) - (6) - (9)   the largest number of talks scheduled.

Step-by-step explanation:

arranging the talks from lowest starting time to the highest ending time.

thus,

1. 9:00 a.m. and 9:45 a.m.
2. 9:30 a.m. and 10:00 a.m.
3. 9:50 a.m. and 10:15 a.m.
4. 10:00 a.m. and 10:30 a.m.
5. 10:10 a.m. and 10:25 a.m.
6. 10:30 a.m. and 10:55 a.m.
7. 10:15 a.m. and 10:45 a.m.
8. 10:30 a.m. and 11:00 a.m.
9. 10:45 a.m. and 11:30 a.m.
10. 10:55 a.m. and 11:25 a.m.
11. 11:00 a.m. and 11:15 a.m.

we start from the earliest time as

9:00 a.m. and 9:45 a.m which is (1).

After the talk is finished we pick the nearest time for another talk which starts at

9:50 a.m. and 10:15 a.m which is (3).

After this talk we again pick the nearest time for another talk which becomes

10:30 a.m. and 10:55 a.m which is (6).

and lastly

10:45 a.m. and 11:30 a.m which is (9).

Note: we didn't choose other times because we cannot talk at 2 or 3 places at the same time. so we pick another when one talk is finished.

thus the answer is (1) - (3) - (6) - (9) as the largest number of talks scheduled.