該問題是一個(gè)經(jīng)典問題，算法導(dǎo)論中的例題。
題意是有若干個(gè)會議要開，每個(gè)會議給定開始時(shí)間s和結(jié)束時(shí)間e，其中任意兩個(gè)會議i和j，若i的時(shí)間和j的時(shí)間有重疊（包括邊界相等情況），則認(rèn)為兩個(gè)會議不能同時(shí)進(jìn)行即沖突，現(xiàn)在要問給定若干個(gè)會議，求最多能有多少會議不沖突，即
最大會議兼容子集的大小。
標(biāo)準(zhǔn)的貪心算法，可以先按照會議結(jié)束時(shí)間排序，然后再依次考慮每個(gè)會議。算導(dǎo)上的證明非常精彩，強(qiáng)烈建議捧讀。
簡單來說就是利用了一個(gè)定理：
對于任意非空子問題S
ij，其中S
ij代表會議i到j(luò)的集合，設(shè)a
m是S
ij中具有最早結(jié)束時(shí)間的會議，則會議a
m在S
ij的最大兼容會議子集中被使用。
其實(shí)該定理就是說明為什么按照會議結(jié)束時(shí)間排序再依次考慮每個(gè)會議就能得出最優(yōu)解。
該定理是這樣被證明的：設(shè)A
ij為S
ij的最大兼容會議子集，且將A
ij中的會議按照結(jié)束時(shí)間遞增排序。又設(shè)a
k為A
ij的第一個(gè)回憶。若a
k = a
m，則定理得證；否則若a
k != a
m，則因?yàn)閍
m是S
ij中結(jié)束時(shí)間最早的會議，所以a
m.finish <= a
k.finish，這樣肯定可以構(gòu)造新的兼容會議子集，B
ij = (A
ij - a
k)
∪ am。而該子集包含的會議個(gè)數(shù)是和Aij的會議個(gè)數(shù)相等的！這就證明了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 }
貪心算法和動態(tài)規(guī)劃算法是算法領(lǐng)域非常重要的兩類算法，需要好好掌握。
posted on 2012-09-16 12:32
myjfm 閱讀(1435)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)