会场安排问题

会场安排问题

问题描述：假设要在足够多的会场里安排一批活动，活动的开始时间和结束时间已知，并希望使用尽可能少的会场。设计一个有效的算法进行安排。

分析：这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，就对应要找的最小会场数。 图的最少着色问题，至今没有有效的算法，但这个问题和图的着色问题有不同，活动的时间区间之间的约束关系转化得到的图，属于区间图。我们可以用贪心策略来解决。

分析解答：

（1）n个活动开始和结束时间分别是s[i]和f[i]，s[i]<f[i]。

（2）把n个活动时间看做直线上n个区间，把所有的s[i]和f[i]按大小排序，得到一个2n的有序数组。count用于统计会场数，遍历数组，统计区间的最大的重叠数目。遇到s[i]，一种活动进栈（相当于要安排一个会场），count数加1，比较当前的会场使用数是否是最大。遇到f[i]，一种活动出栈（相当于一个会场用完，可以作为其他活动用），count数减1，直到把所有的活动都安排好，结束遍历。

由于我们只要得到最少的会场数，遍历数组时，遇到一个s[i]，就把当前的count数加1，遇到对应的f[i]时，就把当前的count数减1，同时记录每次循环时最大的count数，循环结束时，最大的count数就是我们需要的最少颜色数。这个算法的时间复杂度主要是由排序所影响，复杂度为O(N*logN)。

//TimePoint[]数组就是所有的s[i]和f[i]按大小排序的结果
int countUsing = 0;
int maxCount = 0;
for(int i = 0; i < 2*N; ++i)
{
    if(TimePoint[i].type == "Begin")
    {
        ++ countUsing;
        if(countUsing > maxCount)
            maxCount = countUsing;
    }
    else
        -- countUsing;
}

    本文转自阿凡卢博客园博客，原文链接： http://www.cnblogs.com/luxiaoxun/archive/2012/08/06/2624686.html ，如需转载请自行联系原作者