UVa 10020 - Minimal Coverage

链接

传送门

题意

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

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}