选择不相交区间（贪心）

数轴上有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;
}