问题描述

问题描述和分析
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

活动安排问题： 要在所给的活动集合中选出最大的相容活动子集合。

活动安排问题的关键是如何按照一定的顺序安排活动，使得选出的活动间相容并能安排尽量多的活动。

代码实现

#include<iostream>
using namespace std;
void sort(int n,int s[],int f[])//把各个活动的起始时间和结束时间按结束时间非减序排序 
{
	int a,b,i,j;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			if(f[i]>f[j])
			{
				a=f[i];f[i]=f[j];f[j]=a;
				b=s[i];s[i]=s[j];s[j]=b;
				
			}
		}
	 } 
}
int GreedySelect(int n,int s[],int f[],bool A[])
{
	A[1]=true;//将第一个活动先安排
	int j=1,count=1; //count为被安排的节目个数 
	for(int i=2;i<=n;i++){
		if(s[i]>=f[j]){
			A[i]=1;
			j=i;
			count++; 
		}
		else A[i]=0;
	     
	} 
	return count;
}

int main(){
	int n,s[50],f[50];
	bool A[50];
	cout<<"请输入节目数：";
	cin>>n;
	cout<<"请依次输入节目开始的时间和结束的时间：" ;
	for(int i=1;i<=n;i++){
		cin>>s[i]>>f[i];
	} 
	sort(n,s,f);
	cout<<"排完序的活动为："<<endl;
	for(int i=1;i<=n;i++){
		cout<<s[i]<<","<<f[i];
		cout<<"   ";
	}
	cout<<endl;	
	cout<<"安排的节目个数为"<< GreedySelect(n,s,f,A)<<endl;
	cout<<"节目的选取情况：";
	for(int i=1;i<=n;i++)
	cout<<A[i]<<"   "; 
	return 0;
}