目录

POJ 2376 Cleaning Shifts


\(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;
}