该问题是一个经典问题，算法导论中的例题。
题意是有若干个会议要开，每个会议给定开始时间s和结束时间e，其中任意两个会议i和j，若i的时间和j的时间有重叠（包括边界相等情况），则认为两个会议不能同时进行即冲突，现在要问给定若干个会议，求最多能有多少会议不冲突，即
最大会议兼容子集的大小。
标准的贪心算法，可以先按照会议结束时间排序，然后再依次考虑每个会议。算导上的证明非常精彩，强烈建议捧读。
简单来说就是利用了一个定理：
对于任意非空子问题S
ij，其中S
ij代表会议i到j的集合，设a
m是S
ij中具有最早结束时间的会议，则会议a
m在S
ij的最大兼容会议子集中被使用。
其实该定理就是说明为什么按照会议结束时间排序再依次考虑每个会议就能得出最优解。
该定理是这样被证明的：设A
ij为S
ij的最大兼容会议子集，且将A
ij中的会议按照结束时间递增排序。又设a
k为A
ij的第一个回忆。若a
k = a
m，则定理得证；否则若a
k != a
m，则因为a
m是S
ij中结束时间最早的会议，所以a
m.finish <= a
k.finish，这样肯定可以构造新的兼容会议子集，B
ij = (A
ij - a
k)
∪ am。而该子集包含的会议个数是和Aij的会议个数相等的！这就证明了am肯定包含在了Sij的最大兼容会议子集中。
样题见http://acm.nyist.net/JudgeOnline/problem.php?pid=14
代码如下：
1 #include <cstdio>
2 #include <cstdlib>
3
4 #define MAX_EVENT 10005
5
6 struct EVENT {
7 int start;
8 int finish;
9 };
10
11 EVENT event[MAX_EVENT];
12
13 static int cmp(const void *a, const void *b) {
14 EVENT *p = (EVENT *)a;
15 EVENT *q = (EVENT *)b;
16 return p->finish > q->finish;
17 }
18
19 int main() {
20 int m;
21 int n;
22 scanf("%d", &m);
23 while (m--) {
24 scanf("%d", &n);
25 int i;
26 for (i = 0; i < n; ++i) {
27 scanf("%d%d", &(event[i].start), &(event[i].finish));
28 }
29 qsort(event, n, sizeof(EVENT), cmp);
30 int res = 1;
31 int max_finish = event[0].finish;
32 for (i = 1; i < n; ++i) {
33 if (event[i].start > max_finish) {
34 res++;
35 max_finish = event[i].finish;
36 }
37 }
38 printf("%d\n", res);
39 }
40 return 0;
41 }
贪心算法和动态规划算法是算法领域非常重要的两类算法，需要好好掌握。
posted on 2012-09-16 12:32
myjfm 阅读(1378)
评论(0) 编辑 收藏 引用 所属分类:
算法基础