活动安排问题(贪心算法).cpp

活动安排问题 贪心算法 活动安排问题 贪心算法

#include"iostream"
using namespace std;

void   sort(int f[],int n)
{
 int temp;
for(int i=1;i<n;i++)
{

for(int j=0;j<i;j++)
if(f[j]>f[j+1])
{
temp=f[j];
f[j]=f[j+1];
f[j+1]=temp;
}

}
cout<<"the sort result:"<<endl;
for( i=0;i<n;i++)  
cout<<f[i]<<",";
cout<<endl;
}


int  schedule(int s[],int f[],bool a[],int r)
{

int n=1;
int j=0;
a[0]=true;
for(int i=1;i<r;i++)
if(s[i]>=f[j])
{a[i]=true;n++;j=i;}
else
a[i]=false;

cout<<"the least amount meeting place is :"<<n;
return n;

}
void main()
{

  int r;//活动数 
  int p=0;
 
cout<<"please input the activity quantity"<<endl;
cin>>r;
cout<<"please input the start_time"<<endl;
int *st=new int[r+1];
bool *a=new bool[r+1];
for(int i=0;i<r;i++)
cin>>st[i];
cout<<"please inputthe end_time"<<endl;
int *et=new int[r+1];
for(int j=0;j<r;j++)
cin>>et[j];
sort(et, r);
schedule(st,et,a,r);
cin.ignore();
cin.ignore();
cout<<"可以进行的活动为：";
for(i=0;i<r;i++)
  if(a[i]==true)
	  cout<<"  "<<i;
}