Given several segments of line (int the X axis) with coordinates [Li , Ri ]. You are to choose the minimal amount of them, such they would completely cover the segment [0, M].
Input
The first line is the number of test cases, followed by a blank line. Each test case in the input should contains an integer M (1 ≤ M ≤ 5000), followed by pairs “Li Ri” (|Li |, |Ri | ≤ 50000, i ≤ 100000), each on a separate line. Each test case of input is terminated by pair ‘0 0’. Each test case will be separated by a single line.
Output
For each test case, in the first line of output your programm should print the minimal number of line segments which can cover segment [0, M]. In the following lines, the coordinates of segments, sorted by their left end (Li), should be printed in the same format as in the input. Pair ‘0 0’ should not be printed. If [0, M] can not be covered by given line segments, your programm should print ‘0’ (without quotes). Print a blank line between the outputs for two consecutive test cases.
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
解题思路：题目大意是，给定一个m，和一些线段区间线段区间的输入以（0，0）作为结束标记，然后需要我们判断能不能覆盖区间（0，m）不能覆盖就输出“0",能覆盖就输出最少需要的线段数和我们需要哪些线段。这是一个贪心问题。首先我们将输入进来的线段按照左值从小到大进行排序，然后进行贪心，原则是尽量选择线段覆盖长度大的，注意每次贪心后的起点位置。关于具体的实现过程代码中有具体的说明。
程序代码：
#include <iostream> #include <algorithm> #include <cmath> using namespace std; struct node //结构体 { int x; int y; }a[100005],b[100005]; int fun(node a,node b)//排序 { return a.x<b.x; } int main() { int t; cin>>t; while(t--) { cout<<endl; int x,y,m,n=0; cin>>m; while(cin>>x>>y) { if(x==0&&y==0)//结束条件 break; if(y>=0)//可以减少一些不必要的线段 { a[n].x=x; a[n].y=y; n++; } } sort(a,a+n,fun);//排序 cout<<endl; if(a[0].x>0)//排序后判断第一个线段，如果起点最小的线段的x都大于0了，就不用往下面判断了。 cout<<"0"<<endl; int p=1,max=0,sum=1; while(p<n&&a[p].x<=0)//选定我们所需要的最小的线段（要求他的y尽可能的大） { if(a[p].y>a[max].y)//更新所选的线段 max=p; p++; } b[sum].x=a[max].x;//起点线段，，把所需的线段数都保存到b数组中 b[sum].y=a[max].y;//起点线段 p=max;//着重注意，，下次寻找的开始位置就我们取得最优开始线段的下一个线段 while(p<n&&b[sum].y<m)//保证不越界，找到所需最后一个线段的最初位置 { int f=1;//标记 int pmax=max; while(p+1<n&&a[p+1].x<=a[max].y)//保证不越界，并且有覆盖 { f=0; p++; if(a[p].y>a[pmax].y)//更新线段，并且使y尽可能的大 pmax=p; } if(f) break; max=pmax;//更新 sum++;//记录所需的线段数 b[sum].x=a[max].x;//把所需的线段数都保存到b数组中 b[sum].y=a[max].y;//把所需的线段数都保存到b数组中 } if(b[sum].y>=m)//判断最后一线段有没有将所要覆盖的线段覆盖完整 { cout<<sum<<endl; for(int i=1;i<=sum;i++) cout<<b[i].x<<" "<<b[i].y<<endl;; } else cout<<"0"<<endl; if(t) cout<<endl; } return 0; }