算法设计与分析
设有n个活动的集合s={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si，fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si>=fj或者sj>=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（）。A、最早结束的活动优先安排B、最先开始的活动优先安排C、占用资源时间最少的活动优先安排D、占用资源时间最长的活动优先安排
题目
设有n个活动的集合s={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si，fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si>=fj或者sj>=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（）。
- A、最早结束的活动优先安排
- B、最先开始的活动优先安排
- C、占用资源时间最少的活动优先安排
- D、占用资源时间最长的活动优先安排
相似问题和答案
第1题：
资源柱状图（频率图）显示出：
A、 关键路径活动的预期需求
B、 根据工作包进行资源安排
C、 根据活动进行资源安排
D、 按照时间段的预期资源使用状况
第2题：
A、结点不占用时间也不消耗资源
B、结点表示前接活动的完成和后续活动的开始
C、箭线代表活动
D、结点的最早出现时间和最迟出现时间是同一个时间
第3题：
资源柱状图（频率图）显示出：（ ）
A．关键路径活动的预期需求
B．根据工作包进行资源安排
C．根据活动进行资源安排
D．按照时间段的预期资源使用状况
第4题：
B.动态规划
C.贪心
D.回溯
第5题：
（1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。
按每项活动的结束时间进行排序，排在前面的优先满足。
第6题：
历时估算是：
A、 活动的预算历时
B、 使用资源的时间
C、 活动完成的时间
D、 活动开始的时间
第7题：
B 宽度优先（种子染色法）
5．关键路径
几个定义： 顶点1为源点，n为汇点。
a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表示，则Ee[I] = Ve[j];
d. 边活动最晚开始时间 El[I], 若边I由<j,k>表示，则El[I] = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。
求解方法：
a. 从源点起topsort,判断是否有回路并计算Ve;
第8题：
历时估算是：（ ）
A．活动的预算历时
B．使用资源的时间
C．活动完成的时间
D．活动开始的时间
第9题：
[问题1]
基于以上案例，简要叙述最优的活动步骤安排。
[问题2]
基于以上案例，请计算项目的完工时间(详细写出每个活动开始时间、占用资源和完成时间以及项目经理分配资源的过程)。
[问题3]
在制订项目计划的过程中，往往受到资源条件的限制，经常采用资源平衡和资源平滑方法，请简要描述二者的区别。
P2 P3 P5从第一周开始，第四周结束。
P4从第二周开始，到第四周结束。
[问题2]总共4周完成
0-1?P1、P5开始占用资源（R1使用5、R2使用5、R3使用1）
1-2 P1结束P2 P3开始P5继续（R1使用6、R2使用5、R3使用2）
2-3 P4结束P2 P3 P5继续（R1使用1、R2使用5、R3使用2）
3-4 P2结束P2 P3 P4 P5（R1使用1、R2使用5、R3使用2）
[问题3]资源平衡是为了在资源需求与资源供给之间取得平衡，根据资源制约对开始日期和结束日期进行调整的一种技术。如果共享资源或关键资源只在特定时间可用，数量有限，或被过度分配。
资源平滑是对进行模型只能够的活动进行调整，从而使项目资源需求不超过预定的资源限制的一种技术。相对于资源平衡而言，资源平滑不会改变项目关键路径，完工日子也不会延迟。也就是说，活动旨在其自由浮动时间和总浮动时间内延迟。因此，资源平衡技术可能无法实现所有资源的优化。
第10题：
B.Θ(n)
C.Θ(nlgn)
D.Θ(n2)