会场安排问题

问题描述：

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

样例输入

5
1 23
12 28
25 35
27 80
36 50

样例输出

3

贪心策略

1.定义一个结构体（或者类）用来保存需要安排活动的开始时间和结束时间。
2.按照开始时间的先后顺序进行排序， 开始时间早的排在前面。
3.定义一个整数数组（初始化为0，大小为会场个数），用于保存每个会场的结束时间
4.对于每一个活动遍历会场，直到找到一个会场结束时间小于此次活动开始的时间为止。

struct ans{   //定义结构体表示活动 
    int begin,end;
    bool flag; //设置标志 
};
bool cmp(ans a,ans b) {
    return a.begin < b.begin;
}
int arrange(int k,ans *a)
{
    int count=k;        //未安排的活动数量
    int room_avail=0;    //可安排的空闲时间段
    int room_num=0;        //需要的会场数量（作为返回值）
    sort(a+1,a+k,cmp);    //对开始进行非降序排列
    while(count>0)
    {
        for(int i=1;i<=k;i++)
        {
            if((a[i].begin>room_avail)&&(a[i].flag==0))  //如果当前活动未安排并且和会场已有活动不冲突 
            {
                room_avail=a[i].end;  //将当前活动加入该会场并更新会场的空闲时间
                a[i].flag=1;
                count--; 
            }
        }
        room_avail=0;      //将room_avail初始化
        room_num++;       //遍历一次，使用的会场数加一 
    } 
    return room_num; //返回安排的会场数 
}

#include<iostream>
#include<cstdio>
using namespace std;

struct ans{   //定义结构体表示活动 
    int begin,end;
    bool flag; //设置标志 
};

int arrange(int k,ans *a)
{
int count=k,room_avail=0,room_num=0;
while(count>0)
  {
    for(int i=1;i<=k;i++)
    {
        if((a[i].begin>room_avail)&&(a[i].flag==0))  //如果当前活动未安排并且和会场已有活动不冲突 
        {
            room_avail=a[i].end;  //将当前活动加入该会场并更新会场的空闲时间
            a[i].flag=1;
            count--; 
        }
    }
    room_avail=0;  //将room_avail初始化
    room_num++;   //遍历一次，使用的会场数加一 
  } 
    return room_num; //返回安排的会场数 

}
int main()
{
    int k,room_num;
    cin>>k;
    ans a[k+1];
    for(int i=1;i<=k;i++)
    {
        cin>>a[i].begin>>a[i].end;
        a[i].flag=0;
    }

    room_num=arrange(k,a) ;
    cout<<room_num<<endl;
    return 0;
}