\(N\) (\(1 \le N \le 25,000\))只蛤，每只蛤只能在特定时间段工作。
\(T\) (\(1 \le T \le 1,000,000\))个时间段。
找到最少蛤数能覆盖整个时间段。
链接：http://poj.org/problem?id=2376
助攻
- 每个时间段都至少要有一只蛤。
- 每只蛤在结束时间之后结束。比如说有两只蛤工作时间段分别是\((1, 3)\)和\((4, 10)\)。这样被认为时间段是连续的，在\(T = 10\)的时候是可行的。
- 任何时间段之间不能断。
- 用
scanf()作为输入不然超时。
题解
按结束时间排序。对每个区间谈心，找到每只在当前时间段内开始，结束最晚的蛤。因为已经排过序啦，所以只要判断开始时间是不是比当前的时间小，第一个找到的就是了。
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
| #include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> P;
vector<P> v;
int N, T, ans = 0;
struct cmp {
bool operator()(const P &l, const P &r) {
return l.second > r.second;
}
};
void solve() {
sort(v.begin(), v.end(),cmp());
int cur = 1;
bool find = true;
while (cur <= T) {
if ((v.size() == 0) || !find || (v[0].second < cur)) { ans = -1; return ; }
for (int i = 0; i < v.size(); i++) {
if (v[i].first <= cur) {
ans++;
cur = v[i].second+1;
printf("%d %d\n\n", v[i].first, v[i].second);
v.erase(v.begin()+i);
find = true;
break;
}
find = false;
}
}
return ;
}
int main(void) {
scanf("%d %d", &N, &T);
int start, end;
for (int i = 0; i < N; i++) {
scanf("%d %d", &start, &end);
v.push_back(P(start, end));
}
solve();
printf("%d\n", ans);
return 0;
}
|