//貪心算法

#include "stdafx.h"
#include<iostream>
#define N 100
using namespace std;

struct Activity
{
 int number; //活動編號
 int begin; //活動開始時間
 int end; //活動結束時間
 bool flag;//此活動是否被選擇
 int roomNum; //此活動在哪間教室舉行
};
//對于活動集，按照結束時間遞增排序,使用快速排序
void fast_sort(Activity *act,int f,int t)
{
 if(f<t)
 {
 int i = f-1,j = f;
 Activity a = act[t];
 while(j<t)
 {
  if(act[j].end<=a.end)
  {
  i++;
  Activity temp1 = act[i];
  act[i] = act[j];
  act[j] = temp1;
  }
  j++;
 }
 Activity temp2 = act[t];
 act[t] = act[i+1];
 act[i+1] = temp2;
 fast_sort(act,f,i);
 fast_sort(act,i+2,t);
 }
}
//把每一個相容的活動集添加到一個教室，使得教室數目最少
int select_room(Activity *act,int *time,int n)
{
 int i = 1;
 int j = 1;
 int sumRoom;
 //目前所用的教室數目
 sumRoom = 1; 
 int sumAct;
 //目前有多少活動被選擇了
 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;
 }
 }
 return sumRoom;
}

int _tmain(int argc, _TCHAR* argv[])
{
 int cases;
 Activity act[N];
 //用來記錄每個教室目前最晚完成的活動的結束時間
 int time[N];
 cout<<"請輸入案例的個數："<<endl;
 cin>>cases;
 while(cases--)
 {
 int n;
 cout<<"請輸入活動的數目："<<endl;
 cin>>n;
 int i;
 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);
 int roomNum =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");
 return 0;
}