public static int[] GreedyAc(int s[], int f[], int n){
	int x[] = new int[n];
        //默认标记第一个标记位i存入集合A中
	x[0] = 1;
	int j = 0; //j用来表示f数组的下标值
	for(int i = 1; i < n; i++){
		//判断下一个活动的开始时间是否比当前活动的结束时间晚
		if(s[i] >= f[j]){
			x[i] = 1;//标记i位置存入集合A中
			j = i;//i位置存入集合A中，那下次比较f的时候，就从i位置开始，i已经在集合活动中，下一个活动时间要比i来的晚
		}
	}
	return x;
}

//4d1 活动安排问题 贪心算法  
#include "stdafx.h"  
#include <iostream>   
using namespace std;   
  
template<class Type>  
void GreedySelector(int n, Type s[], Type f[], bool A[]);  
  
const int N = 11;  
  
int main()  
{  
    //下标从1开始,存储活动开始时间  
    int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};  
  
    //下标从1开始,存储活动结束时间  
    int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};  
  
    bool A[N+1];  
  
    cout<<"各活动的开始时间,结束时间分别为："<<endl;  
    for(int i=1;i<=N;i++)  
    {  
        cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;  
    }  
    GreedySelector(N,s,f,A);  
    cout<<"最大相容活动子集为："<<endl;  
    for(int i=1;i<=N;i++)  
    {  
        if(A[i]){  
            cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;  
        }  
    }  
  
    return 0;  
}  
  
template<class Type>  
void GreedySelector(int n, Type s[], Type f[], bool A[])  
{  
    A[1]=true;  
    int j=1;//记录第1次加入A中的活动  
  
    for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容  
    {  
        if (s[i]>=f[j])  
        {   
            A[i]=true;  
            j=i;  
        }  
        else  
        {  
            A[i]=false;  
        }  
    }  
}

#include<stdio.h>
# define N 11

void GreadyActivitySelector(int *s,int *f,int *A,int n);
void RecursiveActivitySelector(int *s,int *f,int *A,int i,int n,int k);

void main()
{
	int s[N]={1,3,0,5,3,5,6,8,8,2,12};//开始时间
	int f[N]={4,5,6,7,8,9,10,11,12,13,14};//结束时间
	int A[N]={0};//初始化
	int n=N;
	GreadyActivitySelector(s,f,A,n);//迭代版本
//	RecursiveActivitySelector(s,f,A,0,n,0);//递归版本
	for(int i=0;i<n;i++)
		printf("%d ",A[i]);//被选择的活动 
}

/****************************************************\
函数功能：选择最佳的活动安排
输入：    各个活动的起始时间和结束时间、待存储被选择活动的数组A、活动个数
输出：    无
\****************************************************/

void GreadyActivitySelector(int *s,int *f,int *A,int n)//迭代版本
{
	A[0]=1;
	int	i=0;
	int j=1;
	for(int m=1;m<n;m++)
	{
		if(s[m]>=f[i])//开始时间大于上个活动的结束时间
		{
			i=m;
			A[j]=m+1;//注意下标与第几位差一
			j++;
		}
	}
}