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

---

做法 : Greedy

#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int x, y;
}Seg;
int cmp(const void *i, const void *j) {
    Seg *a, *b;
    a = (Seg *)i, b = (Seg *)j;
    if(a->x != b->x)
        return a->x - b->x;
    return a->y - b->y;
}
int main() {
    int T, M, N, x, y;
    Seg Data[100000];
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &M);
        N = 0;
        while(scanf("%d %d", &x, &y) == 2) {
            if(x == 0 && y == 0)    break;
            Data[N].x = x;
            Data[N].y = y;
            N++;
        }
        qsort(Data, N, sizeof(Seg), cmp);
        Seg Ans[100000];
        int CoverR = 0, NextCoverR = 0, i = 0, Aidx = 0, tmp;
        while(i < N) {
            CoverR = NextCoverR;
            tmp = -1;
            while(i < N && Data[i].x <= CoverR) {
                if(Data[i].y > NextCoverR) {
                    NextCoverR = Data[i].y;
                    tmp = i;
                }
                i++;
            }
            if(tmp < 0)    {
                if(CoverR < M)    Aidx = 0;
                break;
            }
            Ans[Aidx++] = Data[tmp];
            if(NextCoverR >= M)    break;
            i = tmp+1;
        }
        if(Aidx == 0)    puts("0");
        else {
            printf("%d\n", Aidx);
            for(i = 0; i < Aidx; i++)
                printf("%d %d\n", Ans[i].x, Ans[i].y);
        }
        if(T)    puts("");
    }
    return 0;
}