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--;
    }

問題二

小飛看了時間安排，他發現自己感興趣的兩個研究小組的見面會分別被安排在同一天的第一個和最后一個，他覺得不爽，能不能在優化總的見面會時間的基礎上，讓每個同學參加見面會的時間盡量集中？