\(UVa\) \(10020\)

题意：

给你一个\(0\)~\(m\)的区间，然后给你若干线段，问你最少取多少线段可以将0~m完全覆盖

分析：

经典贪心模型

\(Code:\)

#include
#include
#include
#include
#include
using namespace std;
const int maxn=100010;
struct Node
{
int l,r;
bool operator <(const Node& a) const
{
return r>a.r;
}
}a[maxn];
templatevoid read(T &x)
{
bool f=0;char ch=getchar();x=0;
for(;ch<&＃39;0&＃39;||ch>&＃39;9&＃39;;ch=getchar()) if(ch==&＃39;-&＃39;) f=1;
for(;ch>=&＃39;0&＃39;&&ch<=&＃39;9&＃39;;ch=getchar()) x=x*10+ch-&＃39;0&＃39;;
if(f) x=-x;
}
int ans[maxn];
bool vis[maxn];
int main()
{
int T;
read(T);
while(T--)
{
int tot=0;
int x,y;
int m;
memset(ans,0,sizeof(ans));
memset(vis,false,sizeof(vis));
scanf("%d",&m);
while(scanf("%d%d",&x,&y)&&(x||y))
{
if(y<=0||x>=m) continue;
a[++tot].l=x,a[tot].r=y;
}
sort(a+1,a+tot+1);
int r=0;
int cnt=0;
while(r {
bool flag=false;
for(int i=1;i<=tot;++i)
{
if(!vis[i]&&a[i].l<=r&&a[i].r>r)
{
vis[i]=true;
ans[++cnt]=i;
r=a[i].r;
flag=true;
}
}
if(!flag) break;
}
if(r>=m)
{
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i)
{
printf("%d %d\n",a[ans[i]].l,a[ans[i]].r);
}
}
else
{
printf("0\n");
}
}
return 0;
}