URAL 1303. Minimal Coverage

Author: 2015-08-17

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1303

1303. Minimal Coverage

Time limit: 1.0 second
Memory limit: 64 MB
Given set of line segments [Li, Ri] with integer coordinates of their end points. Your task is to find the minimal subset of the given set which covers segment [0, M] completely (M is a positive integer).

Input

First line of the input contains an integer M (1 ≤ M ≤ 5000). Subsequent lines of input contain pairs of integers Li and Ri(−50000 ≤ Li < Ri ≤ 50000). Each pair of coordinates is placed on separate line. Numbers in the pair are separated with space. Last line of input data contains a pair of zeroes. The set contains at least one and at most 99999 segments.

Output

Your program should print in the first line of output the power of minimal subset of segments which covers segment [0, M]. The list of segments of covering subset must follow. Format of the list must be the same as described in input with exception that ending pair of zeroes should not be printed. Segments should be printed in increasing order of their left end point coordinate.
If there is no covering subset then print “No solution” to output.

Samples

input output 
1
-1 0
-5 -3
2 5
0 0

No solution

1
-1 0
0 1
0 0

1
0 1

2. 思路

题目给出一个目标长度M，和若干线段，求能够覆盖区间[0, M]的最少线段。

贪心算法。按照线段起点，对线段列表进行升序排列。然后从前向后遍历线段列表：首先查找起点在0之前的各个线段，在这些线段中，找出终点最远的一条线段，选择该线段，记为L0；然后继续向后查找起点在L0终点之前的各个线段，找出其中终点最远的一条线段，选择该线段，记为L1······以此类推，直到所选线段终点大于M，即得到覆盖[0, M]所需的最少线段。

3. 代码

// #define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MAX_SEGMENT_NUM 99999

typedef struct LineRecord {
    int start, end;
} Line;

void solveE4bMinimalCoverage();
int inputSchedule(Line line[]);
int cmp(const void *a, const void *b);

int main() {
    solveE4bMinimalCoverage();
    return 0;
}

Line line[MAX_SEGMENT_NUM];
void solveE4bMinimalCoverage() {
    int m;
    scanf("%d", &m);

    int n = inputSchedule(line);
    qsort(line, n, sizeof(Line), cmp);

    int lastEnd = 0, cnt = 0, candLineId = 0, candLineEnd = -1;
    int selection[MAX_SEGMENT_NUM];
    for (int i = 0; i < n; ++i) {
        if (line[i].start <= lastEnd) {
            if (line[i].end > candLineEnd) {
                candLineEnd = line[i].end;
                candLineId = i;
                if (candLineEnd >= m) {
                    selection[cnt++] = candLineId;
                    break;
                }
            }
        } else {
            lastEnd = candLineEnd;
            selection[cnt++] = candLineId;

            if (line[i].start <= lastEnd) {
                if (line[i].end > candLineEnd) {
                    candLineEnd = line[i].end;
                    candLineId = i;
                    if (candLineEnd >= m) {
                        selection[cnt++] = candLineId;
                        break;
                    }
                }
            }
        }
    }

    if (candLineEnd < m) {
        printf("No solution\n");
    } else {
        printf("%d\n", cnt);
        for (int i = 0; i < cnt; ++i) {
            printf("%d %d\n", line[selection[i]].start, line[selection[i]].end);
        }
    }
}

int inputSchedule(Line line[]) {
    int n = 0, start, end;

    scanf("%d %d", &start, &end);
    while (start != 0 || end != 0) {
        line[n].start = start;
        line[n].end = end;
        ++n;
        scanf("%d %d", &start, &end);
    }
    return n;
}

int cmp(const void *a, const void *b) {
    if ((*(Line *)a).start != (*(Line *)b).start) {
        return (*(Line *)a).start - (*(Line *)b).start;
    } else {
        return (*(Line *)b).end - (*(Line *)a).end;
    }
}