贪心算法-活动安排问题

动安排问题是一种经典的贪心算法问题，它要求在一系列争用某一公共资源的活动中，选择最大的相容活动子集合，使得尽可能多的活动能兼容地使用公共资源。贪心算法提供了一个简单、漂亮的方法来解决这个问题。

具体来说，活动安排问题描述如下：有n个活动，每个活动都要求使用同一资源，如i活动有起始时间si和一个结束时间fi，且si<fi。j活动起始时间为sj，结束时间为fj，如果i，j活动相容的话则要满足si>fj或者sj>fi。贪心策略是每次选择结束时间最早的那个活动进行安排。

下面是Java语言实现的代码：

//s:起始时间，f:结束时间，a:是否安排
//输入的活动按其结束时间增序排列
public static int greedySelector(int s[],int f[],boolean a[]) {
    int n=s.length-1;
    a[1]=true;//第一个活动安排
    int j=1;
    int count=1;//活动安排个数
    for(int i=2;i<=n;i++) {
        if(s[i]>=f[j]){
            a[i]=true;//如果活动满足则为true
            j=i;//将当前活动序号保存到j中已备下一个活动进行相容检测
            count++;//当前安排活动个数
        } else{
            a[i]=false;//活动不安排
        }
    }
    return count;//返回活动安排个数
}