题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=85904#problem/D
题意：
给出一些区间[Li,Ri],请你找到这些区间的一个子集,使得子集里的区间完全覆盖[0,M].
输入：首行输入案例数。换行后第三行包含一个数M(1<=M<=50000)，其接下来每行包含一对数Li和Ri(|Li|<=50000,|Ri|<=50000),最后以"0 0"结束，案例与案例之间用换行分隔。
输出：输出一个整数k,表示最少需要多少个区间覆盖[0,M],并在接下来的k行将这些区间按照左边数从小到大的顺序排列出。如果无解,则输出"0"，不带引号。不同案例的解使用换行符间隔。
案例：
Sample Input
2
1
-1 0
-5 -3
2 5
0 0
1
-1 0
0 1
0 0
Sample Output
0
1
0 1
分析：
将所给覆盖区间从小到大排序，先比较起点，若一致则比较终点。被覆盖区间的起点是0，那么找出所有区间起点小于0中的最合适的区间。要求用尽量少的区间覆盖，所以选择右端点更大的区间，它包含区间长度更长，更易覆盖。如果在所有覆盖区间中找到了解，但右端点小于M，则把找到的覆盖区间的右端点定为新的覆盖区间的起点。
源代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int M; 6 struct qj//结构体 7 { 8 int l; 9 int r; 10 }a[100010],b[100010];//对象 11 int cmp(const qj &a,const qj &b)//排序 12 { 13 if(a.l!=b.l) return a.l<b.l; 14 else return a.r>b.r; 15 } 16 int main() 17 { 18 int T,x,y,j,max,ans,t; 19 scanf("%d",&T);//案例数 20 while(T--) 21 { 22 memset(a,0,sizeof(a)); 23 memset(b,0,sizeof(b)); 24 int i=0,ant=0,min=0;//ant为覆盖区间数，min为覆盖区间左极限（起点） 25 scanf("%d",&M);//被覆盖区间[0，M] 26 while(scanf("%d%d",&x,&y))//给定分区间 27 { 28 if(!x&&!y) break; 29 a[i].l=x; 30 a[i].r=y; 31 i++; 32 } 33 max=0;//覆盖区间右极限（终点） 34 sort(a,a+i,cmp);//排序 35 while(1) 36 { 37 if(min>=M) break;//覆盖区间超过被覆盖区间 38 ans=0; 39 for(j=0;j<i;j++)//找寻覆盖区间 40 { 41 if(a[j].l<=min) 42 { 43 if(a[j].r>max) 44 { 45 t=j;//标记区间 46 max=a[j].r; 47 ans=1; 48 } 49 } 50 } 51 if(ans)//判断覆盖区间是否满足条件 52 { 53 min=max;//更改起点 54 b[ant]=a[t]; 55 ant++; 56 } 57 else break; 58 } 59 if(ans)//输出控制 60 { 61 printf("%d ",ant); 62 for(i=0;i<ant;i++) 63 printf("%d %d ",b[i].l,b[i].r); 64 } 65 else 66 printf("0 "); 67 if(T) printf(" "); 68 } 69 return 0; 70 }