当前位置 博文首页 > 爱新觉罗?炒饭的博客：活动安排问题（贪心算法）
设有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相容。
活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。
先按照结束时间从小到大排序，排序时还要记得同时交换s[i]的值，安排好第一个活动后，往后查找到某一活动的开始时间大于前面活动的结束时间时，安排此活动，以此类推，直到遍历到所以活动都查了一遍（i=n）
在这里想着练习一下冒泡和选择排序算法，当然如果考试允许，直接调用库函数sort()也行。
#include<iostream>
using namespace std;
void Sort1(int n,int s[],int f[]) //冒泡排序
{
for(int i=1;i<=n-1;i++)
for(int j=i;j<=n-i;j++)
if(f[j]>f[j+1])
{
swap(f[j],f[j+1]);
swap(s[j],s[j+1]);
}
}
void Sort2(int n,int s[],int f[]) //选择排序
{
for(int i=1;i<=n-1;i++)
for(int j=i+1;j<=n;j++)
if(f[i]>f[j])
{
swap(f[j],f[i]);
swap(s[j],s[i]);
}
}
int main()
{
int n,s[100],f[100]; //s[i]表示活动起始时间，f[i]表示活动结束时间
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i]>>f[i];
Sort2(n,s,f);
int A[100],j=1;
A[1]=1;
for(int i=2;i<=n;i++)
{
if(s[i]>=f[j])
{
A[i]=1;
j=i;
}
else
A[i]=0;
}
for(int i=1;i<=n;i++)
if(A[i])
cout<<i<<" ";
return 0;
}
