UVA 10020 - Minimal coverage

[GREEDY]



#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct Line{int L,R;}lines[100010];
int save[100010];
bool operator<(Line a,Line b){return (a.L<b.L);}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int M;scanf("%d",&M);
int lcnt=0; int a,b;
while(scanf("%d %d",&a,&b))
{
if((a==0)&&(b==0)) break;
if(b<0) continue;
lines[lcnt].L=a,lines[lcnt].R=b;
lcnt++;
}
sort(lines,lines+lcnt);
//for(int lx=0;lx<lcnt;lx++)
// printf("%d %d]\n",lines[ptrs[lx].index].L,lines[ptrs[lx].index].R);
int lptr=0;
int Now=0;
int savecnt=0;
while(lptr<lcnt)
{
int mindex=-1;
int mmax=0;
while((lptr<lcnt)&&(lines[lptr].L<=Now))
{
if(mmax<lines[lptr].R)
{
mindex=lptr;
mmax=lines[lptr].R;
}
lptr++;
}
if(mindex<0) break;
Now=mmax;
save[savecnt++]=mindex;
if(Now>=M) break;
lptr=mindex+1;
}
if(Now>=M)
{
printf("%d\n",savecnt);
for(int lx=0;lx<savecnt;lx++)
printf("%d %d\n",lines[save[lx]].L,lines[save[lx]].R);
}
else
puts("0");
if(T) puts("");
}
return 0;
}