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