UVa 10020 - Minimal coverage

链接

传送门

题意

有一个区间\([0,m]\)，给出若干区间\([l_i,r_i]\)，输出最少使用多少个区间可以覆盖\([0,m]\)，同时输出覆盖方法。

思路

区间覆盖类贪心题，按照左端点排序，每次尽可能向右覆盖即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100010;
struct seg {
    int l, r;
    bool operator < (const seg& rhs) const {
        return l < rhs.l;
    }
} a[maxn];
int path[maxn];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int m, n = 0;
        scanf("%d", &m);
        for (;;) {
            scanf("%d%d", &a[n].l, &a[n].r);
            if (!a[n].l && !a[n].r) {
                break;
            }
            ++n;
        }
        sort(a, a + n);
        int l = 0, r = 0, ans = 0;
        for (int i = 0; i < n; ) {
            if (a[i].l <= l) {
                if (a[i].r > r) {
                    path[ans] = i;
                    r = a[i].r;
                    if (r >= m) {
                        ++ans;
                        break;
                    }
                }
                ++i;
            }
            else {
                if (r <= l) {
                    ans = 0;
                    break;
                }
                l = r;
                ++ans;
            }
        }
        ans = r < m ? 0 : ans;
        printf("%d\n", ans);
        for (int i = 0; i < ans; ++i) {
            printf("%d %d\n", a[path[i]].l, a[path[i]].r);
        }
        if (t) {
            puts("");
        }
    }
    return 0;
}