整数区间
请编程完成以下任务：
1.从文件中读取闭区间的个数及它们的描述；
2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。
【输入】
首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。
【输出】
第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。
【样例输入】
4
3 6
2 4
0 2
4 7
【样例输出】
2
【算法分析】
•算法模型：给n个闭区间[ai,bi], 在数轴上选尽量少的点,使每个区间内至少有一个点。
•算法：首先按b1<=b2<=...<=bn排序。每次标记当前区间的右端点x，并右移当前区间指针，直到当前区间不包含x,再重复上述操作。
•如下图，如果选灰色点，移动到黑色点更优。
通俗的想，把区间想成一块块木板，把要找的点想成钉子，如果你的钉子很靠前的话，后面的木板就可能钉不到，每次把钉子钉在你要钉的木板最后，
这样它就能顺便钉更多木板啦
下面代码的看点有 多关键字快排 （本想用结构体，好排序，可是能难赋值修改当前木板的最右端）
【代码】
1 //整数区间 2 #include<iostream> 3 #include<cstdio> 4 #include<cstdlib> 5 using namespace std; 6 int n; 7 int a[10009],b[10009]; 8 void qsort(int,int);//快排 9 void slove();//解决问题 10 int main() 11 { 12 scanf("%d",&n); 13 for(int i=1;i<=n;i++) 14 scanf("%d%d",&a[i],&b[i]);//输入区间的左右端点 15 qsort(1,n); 16 slove(); 17 return 0; 18 } 19 void qsort(int x,int y) 20 { 21 int l=x,r=y,m1=(a[(x+y)/2]),m2=b[(x+y)/2];//m1为左端点的‘中间’，m2为右端点的‘中间’ 22 while(l<=r) 23 { 24 while(b[l]<m2||b[l]==m2&&a[l]<m1)l++;//比中间的小或者如果等于中间的并且左端点按升序排列 25 while(b[r]>m2||b[l]==m2&&a[r]>m1)r--; 26 if(l<=r)//交换 27 { 28 int t; 29 t=b[l];b[l]=b[r];b[r]=t; 30 t=a[l];a[l]=a[r];a[r]=t; 31 l++;r--; 32 } 33 } 34 if(l<y)qsort(l,r); 35 if(r>x)qsort(x,r); 36 } 37 void slove() 38 { 39 int sum=0;//x是目前的右端点 40 for(int i=1,x=-1;i<=n;i++)//x要取个负的，我一开始取得0,是不对的，因为区间左端点取得到0 41 { 42 if(a[i]<=x)continue;//能覆盖就继续 43 sum++;x=b[i];//否则数量+1，修改目前的右端点 44 } 45 printf("%d",sum); 46 }