贪心算法之最大不相交区间数问题

发布时间:2016-12-8 4:15:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"贪心算法之最大不相交区间数问题",主要涉及到贪心算法之最大不相交区间数问题方面的内容,对于贪心算法之最大不相交区间数问题感兴趣的同学可以参考一下。

贪心算法之最大不相交区间数问题 数轴上有n个区间[ai,bi],要求选择尽量多个区间,使得这些区间两两没有公共点。 贪心策略: 按照b1<=b2<=b3…的方式排序,然后从前向后遍历,每当遇到可以加入集合的区间,就把它加入集合。(集合代表解的集合) 证明: 我们对a1,a2……的关系分以下几种情况考虑: 1、a1>a2。   此时区间2包含区间1。这种情况下显然不会选择区间2,因为选择区间1会留下更多的剩余空间。                       不仅区间2如此,以后所有区间中只要有一个 i 满足a1 > ai,i 都不要选。                       即此种情况下,选择区间1是明智的,与策略一致。 2、排除情况1后,一定有a1<=a2<=a3……。 题目描述: 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动,每个时间最多安排一个活动。现在小刘有一些活动计划的时间表,他想尽可能的安排更多的活动,请问他该如何安排。 输入 第一行是一个整型数m(m<100)表示共有m组测试数据。 每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。 随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi<=Ei) 输出 对于每一组输入,输出最多能够安排的活动数量。 每组的输出占一行 样例输入 2 2 1 10 10 11 3 1 10 10 11 11 20 样例输出 1 2 提示 注意:如果上一个活动在t时间结束,下一个活动最早应该在t+1时间开始 AC代码: #include<cstdio> #include<algorithm> #include<vector> using namespace std; class Range { public: int left; int right; bool operator<(const Range& r)const { if(right<r.right) return true; else return false; } }; int main(int argc,char *argv[]) { int i,n,m,end; vector<Range> r; int ans; scanf("%d",&m); while(m--) { ans=0; end=-1; r.clear(); scanf("%d",&n); for(i=0;i<n;i++) { Range temp; scanf("%d%d",&(temp.left),&(temp.right)); r.push_back(temp); } sort(r.begin(),r.end()); for(vector<Range>::iterator it=r.begin();it<r.end();it++) { if(end<(*it).left) { end=(*it).right; ans++; } } //printf("Case %d:\n",count); printf("%d\n",ans); //count++; } return 0; }

上一篇:poj 2785 二分问题 4 Values whose Sum is 0
下一篇:<深入浅出mfc>第9章和第10章

相关文章

相关评论