高效率地安排会面 - 编程之美1.9

http://www.cnblogs.com/baiyanhuang/archive/2011/03/19/1988782.html
在校园招聘的季节里，为了能让学生们更好地了解微软亚洲研究院各研究组的情况，HR部门计划为每一个研究组举办一次见面会，让各个研究组的员工能跟学生相互了解和交流（如图1-4所示）。已知有n位学生，他们分别对m个研究组中的若干个感兴趣。为了满足所有学生的要求，HR希望每个学生都能参加自己感兴趣的所有见面会。如果每个见面会的时间为t，那么，如何安排才能够使得所有见面会的总时间最短？ 最简单的办法，就是把m个研究组的见面会时间依次排开，那我们就要用m * t的总时间，我们有10多个研究小组，时间会拖得很长，能否进一步提高效率？

此题的官方解法是将问题转化为一个已知的图的问题：即图的最少着色问题。
http://www.cnblogs.com/Dzhouqi/p/3346466.html

bool ColoringGraph(int G[][5],int n,int m);
bool IsOk(int G[][5],int color[],int k,int n) ;
int G[5][5]={{0,1,1,0,0},{1,0,1,1,1},{1,1,0,0,1},{0,1,0,0,1},{0,1,1,1,0}};
int _tmain(int argc, _TCHAR* argv[])
{
    int n=5,m=3;
    ColoringGraph(G,n,m);
    return 0;
}
bool ColoringGraph(int G[][5],int n,int m)
    //n是图的定点个数，G是图的连接矩阵，Gij=1说明i定点与j定点有连接。m是最多可以上的色
    //若输出有效上色，返回1，否则返回0
{
    int *color=new int[n];
    
    for(int i=0;i<n;i++)//给每个顶点颜色初始化为0
        color[i]=0;
    int k=0;
    while(k>=0)//k代表顶点个数，当k回溯到0说明已经没有可行解了
    {
        while(color[k]<=m)
        {
            color[k]++;
            if (IsOk(G,color,k,n))
                break;
        }
        if(color[k]<=m && k==n-1)
        {
            cout<<"OK";
            for(int j=0;j<n;j++)
                cout<<color[j];
            return 1;
        }
        else if(color[k]<=m && k<n-1)
        {
            k++;
        }
        else//若k>m,说明此路不同回溯到上一层
        {
            color[k]=0;
            k--;
        }
    }
    return 0;
}
bool IsOk(int G[][5],int color[],int k,int n)  //判断是否有相同色的顶点，与之是一个边的
{
    for(int i=0;i<n;i++)
    {
        if(G[i][k]==1 && color[i]==color[k])
            return false;
    }
    return true;
}

http://www.cppblog.com/jake1036/archive/2011/06/30/149815.html
1) 面试的时候，每次会面都有一个开始时间b[i] 和 结束时间e[i] 。
(2) 现在有一组面试时间数据，现在要求每一个有冲突的时间，都不允许安排在
同一个地点，求出最小需要安排的地点数目。

问题分析：
(1) 首先按照开始时间，将面试时间递增排列。
(2) 依次从第一个约会开始时间开始。 const int N = 4 ;
 struct Time
 {
    int begin ; //开始时间 
    int end   ; //结束时间   
       
 } ;
 bool forbit[N] ; //禁止数组，为false的时候，表示当前该颜色可以使用 
 int maxcolors  ; //当前最大的颜色数目 
 Time times[N] ;
 int color[N] = {0} ;
 int cmp(const void * a , const void * b)
 {
     return ((Time*)a)->begin - ((Time*)b)->begin ;
    
 }
 void init()
 {
   for(int i = 0 ; i < N ; i++)
     {
       cin>>times[i].begin>>times[i].end ; //输入开始时间和结束时间      
     }  
     qsort(times ,N , sizeof(Time)  ,cmp) ;
      //for(i = 0 ; i < N ;i++)
       // forbit[i] = false ;
 }
 bool overlap(const Time & a, const Time & b)
 {
   if(b.begin >= a.begin && b.begin < a.end )
        return true ;
   return false ;
 }
 int arrange()
 {
  maxcolors = 0 ;    
  int i , j , k ;
  for(i = 0 ; i < N ;i++) //循环每一个约会安排 
  {
        
    for(k = 0 ; k < maxcolors ;k++)
    {
      forbit[k] = false ;
    }
    //判断在i之前的节点是否是与i节点有重合的部分 
     for(j = 0 ; j < i ;j++)
     {
        if(overlap(times[j] , times[i])) //判断两者是否相交 
        {
           forbit[color[j]] = true ;                         
        }          
     } 
     for(k = 0 ; k < maxcolors ;k++)
     {
        if(!forbit[k])
            break ;
     }
     if(k < maxcolors)
       color[i] = k ;
     else
       color[i] = maxcolors++ ;
  }  
      return maxcolors ;
 }