区间贪心算法-——活动安排问题-蒲公英云

区间贪心算法-——活动安排问题

问题题目

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

例如：有n个活动，第i个活动开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？

设待安排的11个活动的开始时间和结束时间如下表 (按结束时间的非减序排列)：

i	1	2	3	4	5	6	7	8	9	10	11
s[i]	1	3	0	5	3	5	6	8	8	2	12
f[j]	4	5	6	7	8	9	10	11	12	13	14

算法分析：

由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

c语言源码：

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define max 1000
int greedselect(int a[],int b[],bool t[],int n){
    int i,j=0,cnt=1;    
    t[0]=1;
    printf("(%d,%d)\n",a[0],b[0]);
    for(i=1;i<n;i++){   //每次选择当前的左区间与上一个的右区间进行比较
        if(a[i]>b[j]){   //如果当前的左区间大于上一个的右区间，则加入到活动中
          t[i]=1;
          printf("(%d,%d)\n",a[i],b[i]);
          cnt++;
          j=i;
        }
    }
    return cnt;
}
int main(){
 int k,n,cont;
 bool t[max];
 int a[max],b[max];
 scanf("%d",&n);
for(k=0;k<n;k++){
   scanf("%d%d",&a[k],&b[k]);
   t[k]=0;
}
//memset(t,0,sizeof(t));//这里初始化t数组可以用memset函数
cont=greedselect(a,b,t,n);
printf("%d",cont);
return 0;
}