活动选择问题：
Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.
兼容活动概念：
Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible ifsi ≥ fj and sj ≥ fi
算法导论上提供了两种方法，一种是DP方法， 另一种是贪心算法，同时网上还提供了另一种DP的方法。下面对三种方法进行讲解：
1，算法导论上的DP方法：
先对每个活动ai按照活动结束时间fi从小到大排序，之后按照递归方程进行动态规划
2. 算法导论上的贪心算法：
先对每个活动ai按照活动结束时间fi从小到大排序，每次选择最早结束的活动，
而这个活动的选择需要与前面所选的活动相容。
原始问题是S= S[0,n+1],设活动am1是S[0,n+1]中具有最早结束时间的活动，
下一个问题是S[m1, n+1],设选择活动am2为S[m1,n+1]中最早结束时间的活动，
则下一个子问题是S[m2,n+1],如此继续：
3. 网上提供的DP方法：
Before starting the dynamic programming algorithm itself, we do some precomputation, as follows. We first sort the activities according to finish time, so that f1 <=f2 <=.. <= fn. We also compute, for every activity i, a number H(i) defined as H(i) = max{l<=i-1&& l>=0 && fl<=si} .the maximum value of the empty set is 0. We can compute each value H(i) in time O(log n) using binary search, so all of the precomputation can be done in time O(n log n).
We now perform the four steps of the dynamic programming method.
Step 1:
Describe an array of values we want to compute.
For every integer i, 0 <=i<=n, define A(i) = the largest profit we can get by (feasibly) scheduling activities from {1; 2,.., i}.
The value we are ultimately interested in is A(n).
Step 2:
Give a recurrence.
A(0) = 0.
This is true because if we are not allowed to schedule any activities at all, then the highest profit we can make is 0.
Let 1 <=i <=n. Then A(i) = max{A(i-1); gi + A(H(i))}:
.