uva 10020 - Minimal coverage

Minimal coverage

The Problem

Given several segments of line (int the X axis) with coordinates [L_i,R_i]. You are to choose the minimal amount of them, such they would completely cover the segment [0,M].

The 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 "L_i R_i"(|L_i|, |R_i|<=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.

The 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 (L_i), 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

---

Alex Gevak
September 10, 2000 (Revised 2-10-00, Antonio Sanchez)

O(n) solution 

#include<stdio.h>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int M,A[5001];
vector<pair<int,int> >seq;
bool cmp(pair<int,int>a,pair<int,int>b){
    if(a.first!=b.first)return a.first<b.first;
    return a.second<b.second;
}
void ans(){
    int cur=0,cm=-1,pick=-1,j;
    vector<int>res;
    rep(i,M+1){
        if(DBG)printf("A %d %d\n",i,A[i]);
        if(i<=cur){
            if(A[i]>=0){
                j=A[i];
                if(seq[j].second>cur)
                    if(seq[j].second>cm){           //pick max
                        cm=seq[j].second,pick=j;
                        if(cm>=M)break;
                    }
            }
        }
        else if(pick>=0)res.push_back(pick),cur=cm,cm=-1,i--;
        else break;         //fail
    }
    if(cm>0)res.push_back(pick);
    if(cm>=M){
        printf("%d\n",res.size());
        rep(i,res.size())printf("%d %d\n",seq[res[i]].first,seq[res[i]].second);
    }
    else printf("0\n");
}
int main(){
    int n,a,b;
    bool ll=0;
    cin>>n;
    rep(i,n){
        cin>>M;
        seq.clear();memset(A,-1,sizeof(A));
        while(scanf("%d%d",&a,&b)==2){
            if(a==0&&b==0)break;
            if(a<M&&b>0){if(a<0)a=0;seq.push_back(make_pair(a,b));}
        }
        rep(i,seq.size()){
            int s1=seq[i].second-seq[i].first,s2=0,j;
            if(A[seq[i].first]>=0)j=A[seq[i].first],s2=seq[j].second-seq[j].first;
            if(s1>s2)A[seq[i].first]=i;
        }
        if(ll)printf("\n");ll=1;
        ans();
    }
}