采用C++实现区间图着色问题（贪心算法）实例详解

本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用C++的贪心算法，来确定哪一个活动使用哪一间教室。

对于这个问题也常被称为区间图着色问题，即相容的活动着同色，不相容的着不同颜色，使得所用颜色数最少。

具体实现代码如下：

//贪心算法

#include"stdafx.h"
#include<iostream>
#defineN100
usingnamespacestd;

structActivity
{
intnumber;//活动编号
intbegin;//活动开始时间
intend;//活动结束时间
boolflag;//此活动是否被选择
introomNum;//此活动在哪间教室举行
};
//对于活动集，按照结束时间递增排序,使用快速排序
voidfast_sort(Activity*act,intf,intt)
{
if(f<t)
{
inti=f-1,j=f;
Activitya=act[t];
while(j<t)
{
if(act[j].end<=a.end)
{
i++;
Activitytemp1=act[i];
act[i]=act[j];
act[j]=temp1;
}
j++;
}
Activitytemp2=act[t];
act[t]=act[i+1];
act[i+1]=temp2;
fast_sort(act,f,i);
fast_sort(act,i+2,t);
}
}
//把每一个相容的活动集添加到一个教室，使得教室数目最少
intselect_room(Activity*act,int*time,intn)
{
inti=1;
intj=1;
intsumRoom;
//目前所用的教室数目
sumRoom=1;
intsumAct;
//目前有多少活动被选择了
sumAct=1;
//教室1目前最晚时间为排在最前面的活动的结束时间
time[1]=act[0].end;
//最先结束的活动放在教室1中
act[0].roomNum=1;
for(i=1;i<n;i++)
{
for(j=1;j<=sumRoom;j++)
{
//如果活动act[i]的开始时间大于等于j教室目前的最晚结束时间且此活动还没有被选择，
//则此活动与目前这间教室里面的活动是兼容的，可以加入进去
if((act[i].begin>=time[j])&&(!act[i].flag))
{
//此活动的教室号码
act[i].roomNum=j;
//此活动被选择
act[i].flag=true;
//更新此教室的最晚时间
time[j]=act[i].end;
//被选择的活动数目加1
sumAct++;
}
}
//说明活动没有全部被选择，而所有活动都遍历一遍
//所以需要再加一个教室，从头再遍历
if(sumAct<n&&i==n-1)
{
//从头开始遍历
i=0;
//教室数目加1
sumRoom=sumRoom+1;
}
}
returnsumRoom;
}

int_tmain(intargc,_TCHAR*argv[])
{
intcases;
Activityact[N];
//用来记录每个教室目前最晚完成的活动的结束时间
inttime[N];
cout<<"请输入案例的个数："<<endl;
cin>>cases;
while(cases--)
{
intn;
cout<<"请输入活动的数目："<<endl;
cin>>n;
inti;
for(i=0;i<n;i++)
{
time[i+1]=0;//初始化每个教室目前最晚的时间为0
act[i].number=i+1;
act[i].flag=false;//初始化每个活动都未被选择
act[i].roomNum=0;//初始化每个活动都占用教室
cout<<"活动"<<i+1<<"开始时间：";
cin>>act[i].begin;
cout<<"活动"<<i+1<<"结束时间：";
cin>>act[i].end;
}
fast_sort(act,0,n-1);
introomNum=select_room(act,time,n);
cout<<"所用教室总数为："<<roomNum<<endl;
cout<<"每个活动在哪一个教室中："<<endl;
for(i=0;i<n;i++)
{
cout<<"活动"<<act[i].number<<"在教室"<<act[i].roomNum<<"中"<<endl;
}
}
system("pause");
return0;
}