該問題是一個經典問題，算法導論中的例題。
題意是有若干個會議要開，每個會議給定開始時間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 閱讀(1441)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎