网站建设商标注册多少类目,微信打字赚钱平台30元,扬中话,网站建设维护工作经验数轴上有n个闭区间[ai,bi]。取尽量少的点#xff0c;使得每个区间内都至少有一个点#xff08;不同区间内含的点可以是同一个#xff09;。
贪心策略#xff1a;
按照b1b2b3…#xff08;b相同时按a从大到小#xff09;的方式排序排序#xff0c;从前向后遍历…数轴上有n个闭区间[ai,bi]。取尽量少的点使得每个区间内都至少有一个点不同区间内含的点可以是同一个。
贪心策略
按照b1b2b3…b相同时按a从大到小的方式排序排序从前向后遍历当遇到没有加入集合的区间时选取这个区间的右端点b。
证明
为了方便起见如果区间i内已经有一个点被取到我们称区间i被满足。
1、首先考虑区间包含的情况当小区间被满足时大区间一定被满足。所以我们应当优先选取小区间中的点从而使大区间不用考虑。 按照上面的方式排序后如果出现区间包含的情况小区间一定在大区间前面。所以此情况下我们会优先选择小区间。 则此情况下贪心策略是正确的。
2、排除情况1后一定有a1a2a3……。 对于区间1来说显然选择它的右端点是明智的。因为它比前面的点能覆盖更大的范围。 从而此情况下贪心策略也是正确的。
例题http://acm.nyist.net/JudgeOnline/problem.php?pid287
附代码非此例题代码。和选择不相交区间问题的十分相似 #include stdio.h
#include algorithm
using namespace std;
struct Extent
{int a,b;bool operator (const Extent S)const{return b S.b || b S.b a S.a;}
}A[10002];
int main()
{int z,n,cnt,end;scanf(%d,z);while(z--){cnt 0;end -1;scanf(%d,n);for(int i0;in;i)scanf(%d%d,A[i].a,A[i].b);sort(A,An);for(int i0;in;i){if(end A[i].a){end A[i].b;cnt;}}printf(%d\n,cnt);}return 0;
}
