陕西师大计科院2009级《算法设计与分析》课程论文集
算法设计（贪心算法解决活动安排）
设计者：朱亚君
贪心算法的计算过程如下图所示。

图中每行相应于算法的一次迭代。

阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。

图1贪心算法的计算过程图
若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。

贪心算法并不总能求得问题的整体最优解。

但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。

这个结论可以用数学归纳法证明。

运用贪心算法解决活动安排问题
附录：
贪心算法的实现具体程序如下：
// 贪心算法实现代码 n为活动个数 s为活动开始起始时间队列 f 为活动结束队列 A为已选入集合
import java.util.Scanner;
public class a {
/**
* @param args
*/
static void GreedySelector(int s[],int f[],boolean A[])
{
//第一个活动为结束时间最早进入选入队列
int n=s.length;
A[1]=true;
int j=2;
for(int i=2;i<n;i++)
{
if(s[i]>=f[j])
{
A[i]=true;
j=i;
}
else
A[i]=false;
}
}
static void paixu(int s[],int f[])//进行以结束时间的大小排序
{
int n=s.length;
int m;
for(int i=0;i<n;i++)
for(int j=i;j<n-1;j++)
{
if(f[j]>f[j+1])
{
m=f[j];
f[j]=f[j+1];
f[j+1]=m;//终止时间如果前一个大于后一个就交换位置
陕西师大计科院2009级《算法设计与分析》课程论文集
m=s[j];
s[j]=s[j+1];
s[j+1]=m;//起始时间也同时进行交换位置
}
}
}
static void Output(boolean a[],int s[],int f[])
{
int t=0;
System.out.println("可以安排的活动有以下几个！");
for(int i=0;i<s.length;i++)
{
if(a[i])
{
System.out.print("(");
System.out.print(s[i]+",");
System.out.print(f[i]);
System.out.print("),");
t++;
}
}
System.out.println("；最多可以安排的活动是"+t+"个。

");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
System.out.print("请输入有几场活动！");
int n=in.nextInt();
int s[]=new int[n+1];
System.out.println("请输入每场活动的开始时间（用空格隔开，以回车结束）");
for(int i=1;i<=n;i++)
s[i]=in.nextInt();
int f[]=new int[n+1];
System.out.print("请输入每场活动的结束时间（用空格隔开，一回车结束）");
for(int j=1;j<=n;j++)
f[j]=in.nextInt();
boolean a[]=new boolean[12];
paixu(s,f);
GreedySelector(s,f,a);
Output(a,s,f);
}
}。