1.9 高效率地安排见面会

在校园招聘的季节里，为了能让学生们更好地了解微软亚洲研究院各研究组的情况，HR部门计划为每一个研究组举办一次见面会，让各个研究组的员工能跟学生相互了解和交流（如图1-14所示）。已知有n位学生，他们分别对m个研究组中的若干个感兴趣。为了满足所有学生的要求，HR希望每个学生都能参加自己感兴趣的所有见面会。如果每个见面会的时间为t，那么，如何安排才能够使得所有见面会的总时间最短？

最简单的办法，就是把m个研究组的见面会时间依次排开，那我们就要用m×t的总时间，我们有10多个研究小组，时间会拖得很长，能否进一步提高效率？

分析与解法

解决这种问题，建立合适的模型是第一步。在本题中，如果有任意一位同学对其中两个小组感兴趣，我们则不能把这两个小组的见面会安排在同一个时间内。如果没有同学同时对这两个研究小组感兴趣，它们之间就没有约束。我们可以想到利用图模型来解决这个问题。

我们把每个小组看成是一些散布的点。如果有一位同学同时对两个小组感兴趣，就在这两个小组对应的两个点间加上一条边。所以，如果某个同学同时对k个小组感兴趣，那么这k个小组中任意两个小组对应的顶点之间都要有一条边。例如，有两位同学A和B，他们分别希望参加（1, 2, 3）和（1, 3, 4）小组的见面会。那么，根据上面的构图方法，我们可以得到下面的图1-15。

见面会最少的时间安排就对应于这个图的最少着色问题。图的最少着色问题可以这样描述，对于一个图G（E, V），试用最少的颜色为这个图的顶点着色，使得∀(vi, vj)∈E，有vi和vj颜色不同。这个问题至今没有有效的算法，但可以用下面两个思路求解。

解法一

对顶点1分配颜色1，然后对剩下的n-1个顶点枚举其所有的颜色可能，再一一验证是否可以满足我们的着色要求，枚举的复杂度是O((n-1)n)，验证一种颜色配置是否满足要求需要的时间复杂度是O n2( )。所以总共的时间复杂度是O((n-1)nn2)。时间复杂度高，但是能够保证得到正确的结果。算法的性能提高还在于使用有用的上下界函数剪枝来避免不必要的搜索。

解法二

我们可以尝试对这个图进行K种着色，首先把K设为1，看看有没有合适的方案，再逐渐把K提高。当假设待求解的图之最少着色数远小于图的顶点数时，则这个方法的复杂度要远低于解法一。

当然，我们还可以用启发式算法来得到一个近似解，而不是最优解。

扩展问题

问题一

见面会之后，正式的面试就陆续开始进行了。某一天，在微软亚洲研究院有N个面试要进行，它们的时间分别为[B[i], E[i]]（B[i]为面试开始时间，E[i]为面试结束时间）。假设一个面试者一天只参加一个面试。为了给面试者提供一个安静便于发挥的环境，我们希望将这N个面试安排在若干个面试点。不同的面试在同一个时间不能被安排在同一个面试点。如果你是微软亚洲研究院的HR，现在给定这N个面试的时间之后，你能计算出至少需要多少个面试点吗？请给出一个可行的方案。比如图1-16有4个面试，分别在时间段[1, 5], [2, 3], [3, 4], [3, 6]进行。

刚看完上面的建立图模型思路的读者可能会说，这道题也可以用图模型求解啊。每场面试是一个顶点，如果两场面试时间上有重叠，就用一条边把它们连接起来。这样，这个问题不也转化成一个图的最少着色问题了吗？不错，还是同样的模型。对于这个新的问题，能否在多项式时间复杂度内求出解呢？

不过这个问题和原问题有一点点不同，因为每个面试对应于一个时间区间。由这些时间区间之间的约束关系转化得到的图，属于区间图。我们可以通过贪心策略来解决。算法的思路就是对于所有的面试I[i]=[B[i], E[i]]，按B[i]从小到大排序，然后按顺序对各个区间着色。对当前区间i着色时，必须保证所着的颜色（Color[i]）没有被出现在这个区域之前且时间段与当前区间有重叠的区间用到。假设面试的总数为N，那么相应的代码如清单1-13所示。

代码清单1-13

    int nMaxColors=0, i, k, j;
    for(i=0; i<N; i++)
    {
        for(k=0; k<nMaxColors; k++)
            isForbidden[k]=false;
        for(j=0; j<i; j++)
            if(Overlap(b[j], e[j], b[i], e[i]))
                isForbidden[color[j]]=true;
        for(k=0; k<nMaxColors; k++)
            if(! isForbidden[k])
                break;
        if(k<nMaxColors)
            color[i]=k;
        else
            color[i]=nMaxColors++;
    }
    return nMaxColors；

nMaxColors就是最后返回的所需的最少颜色。isForbidden是对于每个时间区间i，其他时间区间j中开始时间位于这个时间区间之前的且与这个时间区间有重叠的面试所占用的颜色的标识数组。Overlap函数，则是用来判断两个时间区间是否有重叠。

通过简单分析，我们可以知道这个算法的时间复杂度是O（N2）。实际上，这个区间图中每一个顶点所代表的时间区间，是在一个一维的时间轴上顺序排列的。我们只需要找到这个时间轴上的某一个时间点，使包括这个时间点的时间区间个数最多（设为MaxI），那么这个MaxI就是我们要求的值。读者可以自行证明，上面的多项式复杂度算法可以找到这个MaxI。而一个普通的图，没有这种在某个一维轴上顺序排列的性质，所以没办法用这种贪心算法得到最优方案。

此外，相信有些读者已经发现，在上述算法中，查找一个可行颜色的时候，我们遍历了整个isForbidden数组。如果我们使用更高效的存储数据结构（例如，堆），可以进一步把时间复杂度降低到O（N×log2N）。

如果我们只想得到最少所需的颜色数，则把所有的B[i]、E[i]按大小排序，得到一个长度为2×N的有序数组。然后我们遍历这个数组，遇到一个B[i]，就把当前已使用的颜色数目加1，在遇到对应的E[i]时，就把当前已经使用的颜色数目减1。同时记录每次循环时，最多有多少种颜色正被使用（设为MaxColor），循环结束时，MaxColor就是我们需要的最少颜色数。这个算法的时间复杂度主要是由排序所影响，复杂度应为O（N×log2N）。这个算法的代码如清单1-14所示。

代码清单1-14

    /*TimePoints数组就是将所有的B[i], E[i]按大小排序的结果。
    这个数组的元素有两个成员，一个是val，表示这个元素代表的时间点的数值，另一个是type,
    表示这个元素代表的时间点是一个时间段的开始（B[i]），还是结束(E[i])。*/
    int nColorUsing=0, MaxColor=0;
    for(int i=0; i<2 * N; i++)
    {
        if(TimePoints[i].type==“Begin”)
    {
            nColorUsing++;
            if(nColorUsing > MaxColor)
                MaxColor=nColorUsing;
    }
        else
            nColorUsing--;
    }

问题二

小飞看了时间安排，他发现自己感兴趣的两个研究小组的见面会分别被安排在同一天的第一个和最后一个，他觉得不爽，能不能在优化总的见面会时间的基础上，让每个同学参加见面会的时间尽量集中？