這題是greedy。
首先以左端點排序所有線段,一開始邊界的左端為0,所以找所有線段的左端點小於等於0的,然後右端點是最長的,接著把右端點設成邊界的左端,接著又是解決同樣的子問題。
//ignore header files
struct line{
int left,right;
line(int a,int b){
left = a;
right = b;
}
bool operator<(const line & lvalue) const{
return left<lvalue.left;
}
};
int main(int argc, char const* argv[])
{
int n;
while(scanf("%d",&n) != EOF){
for(int g = 0;g<n;g++){
int m;
scanf("%d",&m);
int l,r;
vector<line> v;
while(scanf("%d %d",&l,&r) && !(l == 0 && r == 0)){
v.push_back(line(l,r));
}
sort(v.begin(),v.end());
int currentl = 0;
int currentr = 0;
vector<line> ans;
for(size_t i = 0;i<v.size() ;i++){
int u = -1;
for(;i<v.size()&&v[i].left<= currentl;i++){
if(v[i].right>currentr){
currentr = v[i].right;
u = i;
}
}
if(u == -1)
break;
ans.push_back(v[u]);
if(currentr >= m)
break;
currentl = currentr;
i--;
}
if(currentr<m){
printf("0\n");
}else{
if(g>0)
printf("\n");
printf("%d\n",ans.size());
for(size_t y = 0;y<ans.size();y++)
printf("%d %d\n",ans[y].left,ans[y].right);
}
}
}
return 0;
}