7-58 会场安排问题 分数 20 作者 陈晓梅 单位 广东外语外贸大学 题目来源：王晓东《算法设计与分析》 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个 顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小 会场数。） 输入格式: 第一行有 1 个正整数k，表示有 k个待安排的活动。 接下来的 k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间 以 0 点开始的分钟计。 输出格式: 输出最少会场数。 输入样例: 5 1 23 12 28 25 35 27 80 36 50 输出样例: 在这里给出相应的输出。例如： 3

这道题是典型的贪心算法题目，可以使用贪心思想解决。

首先，我们需要将所有的活动按照结束时间从小到大进行排序，这样可以保证每个会场尽量安排更多的活动。

然后，我们从前往后遍历所有的活动，对于每个活动，我们需要找到一个合适的会场。一个会场是合适的，当且仅当该会场中已安排的所有活动的结束时间都早于当前考虑的活动的开始时间。如果当前有多个合适的会场，我们选择其中结束时间最早的那个会场，这样可以保证给后面的活动留出更多的时间。

如果当前没有合适的会场，我们就需要新开一个会场，将当前的活动安排在这个新的会场中。

最后，我们安排的会场总数就是最少会场数。具体实现可以使用一个优先队列来维护每个会场的结束时间，每次取出结束时间最早的会场来安排活动。

代码如下：