1. 每个人都有开始时间Si和结束时间Fi
2. 每个人开始后无法停留，必须坚持到结束
3. 每次只能一个人运作，就是说下一个必须在前一个完成后才能上
问：
1. 最长时间
2. 最多参与人数
eg：
输入：
3
0 5
0 1
1 3
表示：3人参与，第一人是0时开始，5时结束，依次类推...
数轴表示就是：
0__1__2__3__4__5
0__1
1__2__3
输出：
最长时间：5 （0-5）
最多人数：2 （0-1；1-3）
6 个解决方案
#1
类似活动选择问题，第1问需要动态规划，第2问可以用贪心算法。
#2
将这n个活动按结束时间由小到大排序之后，假设此时有F(1)<=F(2)<=...<=F(n)
1.最长时间
用dp(i,T)来表示在时间T之前完成的、前i个活动所能安排的最长时间。那么状态转移方程：
if( F(i)>T )
dp(i,T)=dp(i-1,T);
else
dp(i,T)=max{ dp(i-1,T)，F(i)-S(i)+dp(i-1,S(i)) };
最后dp(n,F(n))就是题目解。
2.最多参与人数
1)优先选结束时间最早的人；
2)将被选择的人、与刚才选择有冲突的人统统去掉，在剩下的数据中重复1)直到过程结束。
证明过程不再赘述，网上有很多。
1.最长时间
用dp(i,T)来表示在时间T之前完成的、前i个活动所能安排的最长时间。那么状态转移方程：
if( F(i)>T )
dp(i,T)=dp(i-1,T);
else
dp(i,T)=max{ dp(i-1,T)，F(i)-S(i)+dp(i-1,S(i)) };
最后dp(n,F(n))就是题目解。
2.最多参与人数
1)优先选结束时间最早的人；
2)将被选择的人、与刚才选择有冲突的人统统去掉，在剩下的数据中重复1)直到过程结束。
证明过程不再赘述，网上有很多。
#3
帮忙顶一下，让了解的人来解答.
#4
感谢，想起来了！！！嘿嘿，去写下先~等下放分！
#5
哎,帮顶!
#6
Mark...
#1
类似活动选择问题，第1问需要动态规划，第2问可以用贪心算法。
#2
将这n个活动按结束时间由小到大排序之后，假设此时有F(1)<=F(2)<=...<=F(n)
1.最长时间
用dp(i,T)来表示在时间T之前完成的、前i个活动所能安排的最长时间。那么状态转移方程：
if( F(i)>T )
dp(i,T)=dp(i-1,T);
else
dp(i,T)=max{ dp(i-1,T)，F(i)-S(i)+dp(i-1,S(i)) };
最后dp(n,F(n))就是题目解。
2.最多参与人数
1)优先选结束时间最早的人；
2)将被选择的人、与刚才选择有冲突的人统统去掉，在剩下的数据中重复1)直到过程结束。
证明过程不再赘述，网上有很多。
1.最长时间
用dp(i,T)来表示在时间T之前完成的、前i个活动所能安排的最长时间。那么状态转移方程：
if( F(i)>T )
dp(i,T)=dp(i-1,T);
else
dp(i,T)=max{ dp(i-1,T)，F(i)-S(i)+dp(i-1,S(i)) };
最后dp(n,F(n))就是题目解。
2.最多参与人数
1)优先选结束时间最早的人；
2)将被选择的人、与刚才选择有冲突的人统统去掉，在剩下的数据中重复1)直到过程结束。
证明过程不再赘述，网上有很多。
#3
帮忙顶一下，让了解的人来解答.
#4
感谢，想起来了！！！嘿嘿，去写下先~等下放分！
#5
哎,帮顶!
#6
Mark...