活动安排问题.txt

个人笔记 适合初学者 josephus小孩围圈问题 二分搜索 活动安排问题

设有N个活动，其中每个活动都要求使用同一个资源。每个活动i都有一个要求使用资源的起始时间si和一个结束时间fi,且si<fi.如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。
template<class T>
void greedyselector(int n,T s[],T f[],bool a[])
{
a[1]=true;
int j=1;
for(int i=2;i<=n;i++){
  if(s[i]>f[j]){
     a[i]=true;
     j=i;
     }
  else a[i]=false;
  }
}