1、概述:活动安排问题是可以使用贪心算法求解的,该活动问题就是高效的安排一系列争用某一资源的活动。贪心算法这个时候就是尽可能多的兼容使用了公共的资源。
2、举例:设有N个活动的集合E={1,2,...,n},其中每个活动都是要求使用同一个资源,但是在同一个时间内只能是由一个活动使用这个资源。该问题就是看活动是否相容的问题,设I和J两个活动,最后的目的就是在于Si>=Fj(i活动的开始时间大于等于j活动的完成时间),或者说Sj>=Fi(j活动的开始时间大于等于i活动的完成时间)。
3、算法片段:
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(a[i]>=f[j]){ a[i] = true; j = i; count++; } else a[i] = false; } return count; }