贪心算法-会场安排问题的源代码





【问题描述】

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排。

这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。

编程任务：对于给定的 k 个待安排的活动，编程计算使用最少会场的时间表。



【贪心策略】

根据会场安排问题的定义，首先将问题简化为：找出两个活动i和j，若它们满足startTime[i]≥endTime[j]或startTime[j]≥endTime[i]，则称这两个活动相容，即问题转化为：要求找出最多相容会场集合A。

问题简化为对相容会场A的寻找，下面用贪心方法分析过程，根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。那么问题转化为对度量标准的寻找，判断各个数据是否可以包含在解向量中去，然后根据目标函数来选择最优解。

-Greedy algorithm- venue arrangements source code