有若干个活动,第i个开始时间和结束时间是[Si,fi),只有一个教室,活动之间不能交叠,求最多安排多少个活动?
#include <stdio.h>
#include <stdlib.h>
#define N 10000
/*
@活动安排问题
@作者:hjf
*/
void greed(struAcvity a[],int n);
void sort(struAcvity a[],int n);
struct activity
{
int st;
int ft;
int Ans;
};
typedef struct activity struAcvity;
int main()
{
int n,i,j,cnt=;
scanf("%d",&n);
struAcvity a[n];
for(i=;i<n;i++)
scanf("%d %d",&a[i].st,&a[i].ft);
greed(a, n);
//printf("%d\n%d\n%d\n%d\n",a[0].ft,a[1].ft,a[2].ft,a[3].ft);
for(j=;j<n;j++)
if(a[j].Ans==)
cnt++;
printf("%d",cnt);
return ;
}
void greed(struAcvity a[],int n)
{
int i,j,fData=,sData;
for(i=;i<n;i++)
{
a[i].Ans=;
if(a[i].ft<fData)
fData=a[i].ft;
}
sort(a,n);//printf("%d\n",fData);
for(i=;i<n;i++)
{
if(a[i].st>=fData||a[i].ft==fData)
{
a[i].Ans=;
fData=a[i].ft;
}
} }
void sort(struAcvity a[],int n)
{
int i,j,minftIndex;
struAcvity temp;
for(i=;i<n-;i++)
{
minftIndex=i;
for(j=i+;j<n;j++)
if(a[minftIndex].ft>a[j].ft)
minftIndex=j;
if(minftIndex!=i)
{
temp=a[minftIndex];
a[minftIndex]=a[i];
a[i]=temp;
}
}
}