Why is this a greedy algorithm?

Question

I have this question in my text book:

" Suppose that we have a set of activities to schedule among a large number of lecture halls, where any activity can take place in any lecture hall. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall. "

And the answer is given here: http://mitpress.mit.edu/algorithms/solutions/chap16-solutions.pdf

(the firs solution)

And my answer is, why is the algorithm a greedy algorithm?

I think that it is because it makes the (greedy?) choice that you always take an activity and put it into a lecture hall, where there already is one or more activities (if possible), instead of putting the activity into a new empty lecture hall. But I am not sure. :)

Answer 1

Greedy means that you don't reconsider your choices. that makes it very hard to come up with an optimal solution, and it describes the algorithm there.

Answer 2

It's because you do the most with lecture hall 1 before even considering the rest of the problem. In this sense, lecture hall 1 is "greedy".