主观题：Activity Scheduling

Let us consider the following problem: given the set of activities $$S$$, we must schedule them all using the minimum number of rooms.

**Greedy1:** Use the optimal algorithm for the Activity Selection Problem to find the max number of activities that can be scheduled in one room. Delete and repeat on the rest, until no activity is left.

**Greedy2:**
- Sort activities by start time. Open room 1 for $$a_1$$.
- for $$i=2$$ to $$n$$ if $$a_i$$ can fit in any open room, schedule it in that room; otherwise open a new room for $$a_i$$.

Discuss on each of the above algorithms -- will they end up at the optimal solution?







答案：Greedy2 is an optimal algorithm and Greedy1 is not.