数轴上有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……。
在此条件下,如图所示,不论区间1、2的相对位置如何,选择区间1都会为以后的选择留下更大的剩余空间。
从而在此种情况下, 因此选择区间1也是明智的,与策略一致。
经典例题:活动安排问题->http://acm.nyist.net/JudgeOnline/problem.php?pid=14
附代码。
#include <stdio.h> #include <algorithm> using namespace std; struct Extent { int a,b; bool operator < (const Extent& S)const { return b < S.b; } }A[10002]; int main() { int z,n,cnt,end; scanf("%d",&z); while(z--) { cnt = 0; end = -1; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&A[i].a,&A[i].b); sort(A,A+n); for(int i=0;i<n;i++) { if(end < A[i].a) { end = A[i].b; cnt++; } } printf("%d\n",cnt); } return 0; }