The interval graph coloring problem (greedy algorithm) is solved by C++

The algorithm described in this paper assumes that many classrooms are used to schedule a group of activities. We want to use as few classrooms as possible to schedule all activities. Use C++ greedy algorithm to determine which activities use which classroom.

For this problem is also often referred to as the interval graph coloring problem, that is, the compatible active with the same color, the incompatible with different colors, so that the minimum number of colors used.

The specific implementation code is as follows:

//Greedy algorithm

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

struct Activity
{
 int number; //Activity number
 int begin; //Activity start time
 int end; //End time
 bool flag;//Whether this activity is selected
 int roomNum; //In which classroom will the activity be held
};
//For an active set, sort by end time incrementally, using quicksort
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);
 }
}
//Add each compatible activity set to a classroom to minimize the number of classrooms
int select_room(Activity *act,int *time,int n)
{
 int i = 1;
 int j = 1;
 int sumRoom;
 //Number of classrooms currently in use
 sumRoom = 1; 
 int sumAct;
 //How many activities are currently selected
 sumAct = 1; 
 //Classroom 1 the latest time is the end time of the first activity
 time[1] = act[0].end; 
 //The activities that finish first are in classroom 1
 act[0].roomNum = 1; 
 for(i=1;i<n;i++)
 {
 for(j=1;j<=sumRoom;j++)
 {
  //If the start time of activity act[I] is greater than or equal to the current latest end time of classroom j and the activity has not been selected,
  //Then this activity is compatible with the current activities in this classroom and can be joined
  if((act[i].begin>=time[j])&&(!act[i].flag))
  {
  //The classroom number for this activity
  act[i].roomNum = j;
  //This activity is selected
  act[i].flag = true;
  //The latest time to update this classroom
  time[j] = act[i].end;
  //The number of selected activities is increased by 1
  sumAct ++;
  }
 }
 //Indicates that the activities are not all selected, and that all activities are traversed
 //So we need to add another classroom and do it all over again
 if(sumAct<n&&i==n-1)
 {
  //Start from scratch
  i = 0;
  //Number of classrooms plus 1
  sumRoom = sumRoom+1;
 }
 }
 return sumRoom;
}

int _tmain(int argc, _TCHAR* argv[])
{
 int cases;
 Activity act[N];
 //It is used to record the end time of the latest activities completed in each classroom
 int time[N];
 cout<<" Please enter the number of cases: "<<endl;
 cin>>cases;
 while(cases--)
 {
 int n;
 cout<<" Please enter the number of activities: "<<endl;
 cin>>n;
 int i;
 for(i=0;i<n;i++)
 {
  time[i+1] = 0; //The latest time to initialize each classroom is 0
  act[i].number = i+1;
  act[i].flag = false;  //Initializing each activity is not selected
  act[i].roomNum = 0; //Initialize each activity to occupy the classroom
  cout<<" activity "<<i+1<<" Start time: ";
  cin>>act[i].begin;
  cout<<" activity "<<i+1<<" End time: ";
  cin>>act[i].end;
 }
 fast_sort(act,0,n-1);
 int roomNum =select_room(act,time,n);
 cout<<" The total number of classrooms used is: "<<roomNum<<endl;
 cout<<" In which classroom is each activity: "<<endl;
 for(i=0;i<n;i++)
 {
  cout<<" activity "<<act[i].number<<" In the classroom "<<act[i].roomNum<<" In the "<<endl;
 }
 }
 system("pause");
 return 0;
}