题目：
有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。 每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。 如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。 该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。 例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
这道题用贪心策略来求解
1.首先将n个活动的开始时间与结束的时间都放在一个结构体中，并且为这个结构体根据每个活动的结束时间进行升序排序
2.此时第一个最早结束的为第一个活动，之后第二个活动开始进行遍历用其开始时间与之前的结束时间进行比较，若是大于等于之前的结束时间，那么就会将这个活动计算在内，此时下一个比较的就是这个新的活动的结束时间
3.最后得出有限时间内最多参加活动的数量
简而言之就是根据结束时间排序，然后从第二个开始不断与最近活动的结束时间进行比较，若是符合就加入活动数中
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int n; //输入活动的总数 struct Act{ int start; int end; }act[10000]; bool cmp(Act x,Act y){ return x.end<y.end; } //求出对应时间内可以做的最多事情 int greed_activity(){ int num=1,i=1;0 //默认从第二件开始，之前已经按照最早的结束时间排序过了 for(int j=2;j<=n;j++){ if(act[j].start>=act[i].end){ i=j; num++; } } return num; } void print(Act x) { cout<<"stat:"<<x.start<<" end:"<<x.end<<endl; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&act[i].start,&act[i].end); } act[0].start=-1; act[0].end = -1; sort(act+1,act+n+1,cmp); //按照活动的最晚结束时间进行排序 //for_each(act+1,act+n+1,print); 遍历算法调用库中进行检验 int num = greed_activity(); cout<<num; return 0; }
