給定n個(gè)活動(dòng)，已知它們的起止時(shí)間，如何選擇活動(dòng)能夠使得單個(gè)人能夠完成最多數(shù)量的活動(dòng)，假設(shè)單個(gè)人同一個(gè)時(shí)間只能做單個(gè)活動(dòng)。
例1：考慮下面三個(gè)活動(dòng)，
| 活動(dòng) | 開始時(shí)間 | 結(jié)束時(shí)間 |
|---|---|---|
| 活動(dòng)1 | 10 | 20 |
| 活動(dòng)2 | 12 | 25 |
| 活動(dòng)3 | 20 | 30 |
則單人最多可以完成兩個(gè)活動(dòng)：1和3
例2：考慮下面六個(gè)活動(dòng)，
| 活動(dòng) | 開始時(shí)間 | 結(jié)束時(shí)間 |
|---|---|---|
| 活動(dòng)1 | 1 | 2 |
| 活動(dòng)2 | 3 | 4 |
| 活動(dòng)3 | 0 | 6 |
| 活動(dòng)4 | 5 | 7 |
| 活動(dòng)5 | 8 | 9 |
| 活動(dòng)6 | 5 | 9 |
則最多可以完成四個(gè)活動(dòng)：1，2，4，5
思路是使用貪心方法，首先將活動(dòng)按照結(jié)束時(shí)間進(jìn)行排序，每次都選擇結(jié)束時(shí)間最近的的活動(dòng)，但要保證當(dāng)前選擇的活動(dòng)開始時(shí)間不早于前一活動(dòng)的結(jié)束時(shí)間。
證明：（反證法）
首先將活動(dòng)安裝結(jié)束時(shí)間排序，假設(shè)存在更多的新的活動(dòng)選擇。則某個(gè)時(shí)間點(diǎn)選擇的不是當(dāng)前可行的最近可以完成的活動(dòng)，后面的所有可行活動(dòng)選擇都可能被選擇，所以新的選擇活動(dòng)總數(shù)量不會(huì)大于按照結(jié)束時(shí)間選擇的活動(dòng)總數(shù)量。矛盾。
