贪心算法-会场安排问题

佚名 6年前 (2018-10-14) 算法 1286人围观抢沙发百度已收录

问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点，不相容活动间用边相连。使用相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数）。

[之所以想记录这个问题，就在于括号内的描述。看完题目的描述，我心想：图着色问题不是有一个四色定理。换而言之，即任何活动，只要四个会场就够了。而这显然不符合常理。后来发现，问题在于四色定理只适用于地图，在地图上最多四个国家相互接壤。而活动显然不满足这个条件]

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

算法描述：

算法实现：

#include<stdio.h>
#include<stdlib.h>
void makemap(int **map,int *early,int *late,int n)
{
    for(int i=0;i<n;i++)//当前被判断活动
        for(int j=i+1;j<n;j++)//其余活动
        {
            if((early[i]>=early[j]&&early[i]<=late[j])||
(late[i]>=early[j]&&late[i]<=late[j]))
            {//判断当前活动与其余活动是否交叉  
                map[i][j]=map[j][i]=1;//交叉的话在图上做标记
                map[i][i]++;//记录与当前活动交叉活动的数目
                map[j][j]++;
            }
        }
}//标记交叉活动
void sortpoint(int **map,int *node,int low,int high)
{
 int i,j,temp,t,x;
 if(low<high)
 {
  t=rand()%(high-low+1)+low;
  temp=node[t];
  node[t]=node[low];
  node[low]=temp;

  i=low;
  j=high;
  x=node[i];
  do
  {
   while(i<j && map[node[j]][node[j]]>=map[x][x]) j--;
   if(i<j) {node[i]=node[j];i++;}
   while(i<j && map[node[i]][node[i]]<map[x][x]) i++;
   if(i<j) {node[j]=node[i];j--;} 
  }while(i!=j);
  node[i]=x;
  sortpoint(map,node,low,i-1);
  sortpoint(map,node,i+1,high);
 }
}//依照活动与其他活动交叉的数目对活动进行随机快速排序
 //形成递增序列
void colorit(int **map,int *node,int n)
{
    int *color;
    color=(int *)malloc((sizeof(int))*n);
    for(int i=0;i<n;i++)color[i]=0;
    color[node[n-1]]=0;    
    for(int i=n-2;i>=0;i--)
    {
        int elem[5]={0,0,0,0,0};
        for(int j=i+1;j<n;j++)
          if(map[i][j])elem[color[j]]=1;
       //根据图五色原理
       //设置数组标记与当前活动交叉且已分配会场的活动的举办会场
        for(int j=0;j<5;j++)
          if(elem[j]==0)
          {
              color[i]=j;
              break;
          }
       //根据标记会场数组分配当前活动举办会场
    }
    int count=0;
    for(int i=0;i<n;i++)
        if(color[i]>count)count=color[i]; 
    count++;
    printf("%d",count);
    //统计开设会场的数目（结果） 
}//为每个活动分配会场
int main()
{
    int n;
    scanf("%d",&n);
   //活动数目n
    int **map;
    map=(int **)malloc((sizeof(int *))*n);
    for(int i=0;i<n;i++)
    map[i]=(int *)malloc((sizeof(int))*n);
    //用于记录活动间的交叉情况
    int *early;
    int *late;
    early=(int *)malloc((sizeof(int))*n);
    late=(int *)malloc((sizeof(int))*n);
    //用于记录活动的开始时间和结束时间
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&early[i],&late[i]);
        for(int j=0;j<n;j++)map[i][j]=0;
    }
    makemap(map,early,late,n);
    int *node;
    node=(int *)malloc((sizeof(int))*n);
    for(int i=0;i<n;i++)node[i]=i;
    sortpoint(map,node,0,n-1);
    colorit(map,node,n);    
    return 0;
}