（1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。

题目

（1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。

相似考题

1.现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该问题的基本思路如下(假设需要场地数为m,活动数为n,场地集合为P1，P2,…,Pm),初始条件Pi均无活动安排:(1)采用快速排序算法对n个活动的开始时间从小到大排序,得到活动a1，a2,…，an。对每个活动ai，i从1到n,重复步骤(2)、(3)和(4)；(2)从p1开始,判断ai与P1的最后一个活动是否冲突,若冲突,考虑下一个场地P2,…；(3)一旦发现ai与某个Pj的最后一个活动不冲突,则将ai安排到Pj,考虑下一个活动；(4)若ai与所有己安排活动的Pj的最后一个活动均冲突,则将ai安排到一个新的场地,考虑下一个活动；(5)将n减去没有安排活动的场地数即可得到所用的最少场地数算法首先采用了快速排序算法进行排序,其算法设计策略是( )；后面步骤采用的算法设计策略是(请作答此空)。整个算法的时间复杂度是( )。下表给出了n=11的活动集合,根据上述算法,得到最少的场地数为( )。 A.分治 B.动态规划 C.贪心 D.回溯

2.绘制网络图应遵循的原则不包括（ ）。A.网络图是有向、有序的，从左至右，不能出现回路 B.两个节点之间只能出现一个活动 C.如果若干活动有一个共同的开始和完工活动，并交由一个单位去完成，可以集中成一个活动，并以最长的时间作为该活动的历时 D.如果若干活动有一个共同的开始和完工活动，并交由一个单位去完成，可以集中成一个活动，并以最短的时间作为该活动的历时

3.绘制网络图应遵循的原则不包括()。A:网络图是有向、有序的，从左至右，不能出现回路 B:两个节点之间只能出现一个活动 C:如果若干活动有一个共同的开始和完工活动，并交由一个单位去完成，可以集中成一个活动，并以最长的时间作为该活动的历时 D:如果若干活动有一个共同的开始和完工活动，并交由一个单位去完成，可以集中成一个活动，并以最短的时间作为该活动的历时

4.现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该问题的基本思路如下(假设需要场地数为m,活动数为n,场地集合为P1，P2,…,Pm),初始条件Pi均无活动安排:(1)采用快速排序算法对n个活动的开始时间从小到大排序,得到活动a1，a2,…，an。对每个活动ai，i从1到n,重复步骤(2)、(3)和(4)；(2)从p1开始,判断ai与P1的最后一个活动是否冲突,若冲突,考虑下一个场地P2,…；(3)一旦发现ai与某个Pj的最后一个活动不冲突,则将ai安排到Pj,考虑下一个活动；(4)若ai与所有己安排活动的Pj的最后一个活动均冲突,则将ai安排到一个新的场地,考虑下一个活动；(5)将n减去没有安排活动的场地数即可得到所用的最少场地数算法首先采用了快速排序算法进行排序,其算法设计策略是( )；后面步骤采用的算法设计策略是( )。整个算法的时间复杂度是(请作答此空)。下表给出了n=11的活动集合,根据上述算法,得到最少的场地数为( )。 A.Θ(lgn) B.Θ(n) C.Θ(nlgn) D.Θ(n2)

更多“（1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。”相关问题

  • 第1题：

    下面关于求关键路径的说法不正确的是()。

    A.求关键路径是以拓扑排序为基础的
    B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
    C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
    D.关键活动一一定位于关键路径上

    答案：C
    解析：
    最迟开始时间应等于本工作的最迟完成时间与其持续时间之差。

  • 第2题：

    现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动 A 从 1 时间开始,5 时间结束,活动 B 从 5 时间开始,8 时间结束,则活动 A 和 B 不冲突。现要计算 n 个活动需要的最少场地数。求解该问题的基本思路如下（假设需要场地数为 m,活动数为 n,场地集合为 P1，P2,…,Pm）,初始条件 Pi均无活动安排:（1）采用快速排序算法对 n 个活动的开始时间从小到大排序,得到活动 a1，a2,…，an。对每个活动 ai，i 从 1 到 n,重复步骤（2）、（3）和（4）；（2）从 p1开始,判断 ai与 P1的最后一个活动是否冲突,若冲突,考虑下一个场地 P2,…；（3）一旦发现 ai与某个 Pj的最后一个活动不冲突,则将 ai安排到 Pj,考虑下一个活动；（4）若 ai与所有己安排活动的 Pj的最后一个活动均冲突,则将 ai安排到一个新的场地,考虑下一个活动；（5）将 n 减去没有安排活动的场地数即可得到所用的最少场地数算法首先采用了快速排序算法进行排序,其算法设计策略是（ ）；后面步骤采用的算法设计策略是（ ）。整个算法的时间复杂度是（请作答此空）。下表给出了 n=11 的活动集合,根据上述算法,得到最少的场地数为（ ）。


    A.Θ（lgn）
    B.Θ（n）
    C.Θ（nlgn）
    D.Θ（n2）

    答案：C
    解析：
    快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O (nlogn)。场地上可以安排活动1、8、11为一个场地；活动2、6、9一个场地；活动3为一个场地；活动4、7为一个场地；活动5、10为一个场地，共5个场地。

  • 第3题：

    关于全店铺打折工具，以下选项错误的是：（）

    • A、提前小时创建活动，活动开始和结束时间必须在同一个月内，但是可以提前创建下个月的活动
    • B、提前24小时创建活动，活动开始和结束时间必须在同一个月内，但是可以提前创建个月的活动
    • C、对全店铺的商品按照商品分组设置不同的促销折扣，吸引更多流量
    • D、如果选择了月末的最后一天，需要再选择时间是23：00，否则该活动会在最后一天的0点就结束了

    正确答案:B

  • 第4题：

    活动持续时间估算中，不能包括下列哪个（）

    • A、在下一个活动的开始时间与本活动的结束时间之间的时间
    • B、完成本活动所需的工作时段数
    • C、时间的可能变动区间
    • D、存在不确定性的工作时段数估计

    正确答案:A

  • 第5题：

    在箭线式网络图中，叙述不正确的是（）。

    • A、网络图中任何一个结点都表示前一活动的结束和后一活动的开始
    • B、活动的总时差越大，则表明该活动在整个网络中的机动时间也越大
    • C、活动的最早开始时间等于该活动箭尾事项的最早开始时间
    • D、结点时差等于0的结点称为关键结点

    正确答案:A

  • 第6题：

    设有n个活动的集合s={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si，fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si>=fj或者sj>=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（）。

    • A、最早结束的活动优先安排
    • B、最先开始的活动优先安排
    • C、占用资源时间最少的活动优先安排
    • D、占用资源时间最长的活动优先安排

    正确答案:C

  • 第7题：

    在绘制网络图时，下面正确的说法是（）

    • A、每项活动由且仅有一个箭头表示
    • B、箭头代表开始，箭尾代表活动结束
    • C、一个圆圈代表指向它的活动开始
    • D、箭头的长度和斜度与活动的持续时间或重要性有关

    正确答案:A

  • 第8题：

    一个项目有7个活动：A，B，C，D，E，F，和G。ABD可以在任何时候开始，A需要3周，B5周，D11周。AB结束后C才可以开始。C需要6周。BCD结束后E才能开始。E需要2周。F需要4周，需要在C完成之后才能开始。E完成之后G才能开始。G需要3周。FG完成之后项目才最终完成。那么：（）

    • A、活动A有2周的浮动时间，F有1周的是浮动时间
    • B、活动F有1周的浮动时间
    • C、整个项目没有浮动时间
    • D、活动A有8周的浮动时间

    正确答案:A

  • 第9题：

    活动A历时为3天，开始于4号星期一上午，后续活动B和A的关系为结束一开始。结束一开始关系有3天滞后，活动B历时为4天，星期天为非工作日，从这些数可以得到什么？（）

    • A、两个活动总历时为8天
    • B、活动A开始日期和活动B结束的日历时间为11天
    • C、活动B结束日期为13号星期三
    • D、活动A开始日期和活动B结束的日历时间为14天

    正确答案:B

  • 第10题：

    单选题
    设有n个活动的集合s={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si，fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si>=fj或者sj>=fi。应怎样对这n个活动进行安排才能令最多的活动可以使用资源？（）。
    A

    最早结束的活动优先安排

    B

    最先开始的活动优先安排

    C

    占用资源时间最少的活动优先安排

    D

    占用资源时间最长的活动优先安排


    正确答案： C
    解析： 暂无解析

  • 第11题：

    单选题
    一个项目有7个活动：A，B，C，D，E，F，和G。ABD可以在任何时候开始，A需要3周，B5周，D11周。AB结束后C才可以开始。C需要6周。BCD结束后E才能开始。E需要2周。F需要4周，需要在C完成之后才能开始。E完成之后G才能开始。G需要3周。FG完成之后项目才最终完成。那么：（）
    A

    活动A有2周的浮动时间，F有1周的是浮动时间

    B

    活动F有1周的浮动时间

    C

    整个项目没有浮动时间

    D

    活动A有8周的浮动时间


    正确答案： D
    解析： 暂无解析

  • 第12题：

    多选题
    下列选项中叙述正确的有（　　）。
    A

    某项活动的最早开始时间必须早于直接指向这项活动的所有活动的最早结束时间中的最晚时间，或者与之相同

    B

    某项活动的最迟结束时间必须早于该活动直接指向的所有活动的最迟开始时间的最早时间，或者与之相同

    C

    时差等于最迟结束时间与最早结束时间的差值

    D

    自由时差是指在不影响后序活动最晚开始时间和有关时限的前提下，一项活动可以利用的机动时间

    E

    时差等于最迟开始时间与最早开始时间之间的差值


    正确答案： A,D
    解析：
    A项，某项活动的最早开始时间必须晚于晚于直接指向这项活动的所有活动的最早结束时间中的最晚时间，或者与之相同；D项，自由时差是指在不影响后序活动最早开始时间和有关时限的前提下，一项活动可以利用的机动时间。

  • 第13题：

    现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动 A 从 1 时间开始,5 时间结束,活动 B 从 5 时间开始,8 时间结束,则活动 A 和 B 不冲突。现要计算 n 个活动需要的最少场地数。求解该问题的基本思路如下（假设需要场地数为 m,活动数为 n,场地集合为 P1，P2,…,Pm）,初始条件 Pi均无活动安排:（1）采用快速排序算法对 n 个活动的开始时间从小到大排序,得到活动 a1，a2,…，an。对每个活动 ai，i 从 1 到 n,重复步骤（2）、（3）和（4）；（2）从 p1开始,判断 ai与 P1的最后一个活动是否冲突,若冲突,考虑下一个场地 P2,…；（3）一旦发现 ai与某个 Pj的最后一个活动不冲突,则将 ai安排到 Pj,考虑下一个活动；（4）若 ai与所有己安排活动的 Pj的最后一个活动均冲突,则将 ai安排到一个新的场地,考虑下一个活动；（5）将 n 减去没有安排活动的场地数即可得到所用的最少场地数算法首先采用了快速排序算法进行排序,其算法设计策略是（ ）；后面步骤采用的算法设计策略是（ ）。整个算法的时间复杂度是（ ）。下表给出了 n=11 的活动集合,根据上述算法,得到最少的场地数为（请作答此空）。


    A.4
    B.5
    C.6
    D.7

    答案：B
    解析：
    快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O (nlogn)。场地上可以安排活动1、8、11为一个场地；活动2、6、9一个场地；活动3为一个场地；活动4、7为一个场地；活动5、10为一个场地，共5个场地。

  • 第14题：

    活动持续时间估算中，不能包括下列哪个？（ ）

    A.在下一个活动的开始时间与本活动的结束时间之间的时间
    B.完成本活动所需的工作时段数
    C.时间的可能变动区间
    D.存在不确定性的工作时段数估计

    答案：A
    解析：

  • 第15题：

    确定一个活动的最早开始或完成时间，应遵循的规则是什么？确定一个活动的最迟开始或完成时间，应遵循的规则是什么？


    正确答案: 根据项目的最早开始时间来确定项目的最早完成时间。最早完成时间可在这项活动最早开始时间的基础上加上这项活动的期望活动工期进行计算。计算每项活动的最迟完成时间时，应以项目预计完成时间为参照点进行逆向计算，对于中间的活动，其活动的最迟完成时间就是其后置活动的最迟开始时间的最早时间。最迟开始时间可在该活动最迟完成时问的基础上减去该活动的期望活动工期得出。

  • 第16题：

    结束－开始关系表示紧后活动的开始时间受紧前活动结束时间的制约。


    正确答案:正确

  • 第17题：

    在一个空间安排n=5个活动，开始时间和结束时间分别为[8，10），[12，14），[9，11：30），[11：40，13），[13：30，15）。写出活动安排贪心算法的运行结果。


    正确答案: 1）按照结束时间排序
    [8，10）1，[9，11：30）3，[11：40，13）4，[12，14）2，[13：30，15）5
    2）可行解1，4，5

  • 第18题：

    在网络图中，对于每一个活动需要确定的时间有（）。

    • A、最早开始时间
    • B、最早结束时间
    • C、最迟开始时间
    • D、最迟结束时间

    正确答案:A,B,C,D

  • 第19题：

    某项活动T的工期是5天，其前置活动有A、B、C三个活动，如果活动ABC的最早完成时间分别为4、5、6天，则下面正确的描述是（）

    • A、活动T的最早结束时间是第6天
    • B、活动T的最早结束时间是第11天
    • C、活动T的最迟开始时间是第4天
    • D、活动T的最迟开始时间是第11天

    正确答案:B

  • 第20题：

    时间绩效的选择应该集中在监控（）上，而不是监控活动完成的百分比。

    • A、活动开始
    • B、活动结束
    • C、活动的开始和结束
    • D、活动的机动时间

    正确答案:C

  • 第21题：

    多选题
    在网络图中，对于每一个活动需要确定的时间有（）。
    A

    最早开始时间

    B

    最早结束时间

    C

    最迟开始时间

    D

    最迟结束时间


    正确答案： C,D
    解析： 暂无解析

  • 第22题：

    单选题
    在箭线式网络图中，叙述不正确的是（）。
    A

    网络图中任何一个结点都表示前一活动的结束和后一活动的开始

    B

    活动的总时差越大，则表明该活动在整个网络中的机动时间也越大

    C

    活动的最早开始时间等于该活动箭尾事项的最早开始时间

    D

    结点时差等于0的结点称为关键结点


    正确答案： D
    解析： 暂无解析

  • 第23题：

    问答题
    在一个空间安排n=5个活动，开始时间和结束时间分别为[8，10），[12，14），[9，11：30），[11：40，13），[13：30，15）。写出活动安排贪心算法的运行结果。

    正确答案： 1）按照结束时间排序
    [8，10）1，[9，11：30）3，[11：40，13）4，[12，14）2，[13：30，15）5
    2）可行解1，4，5
    解析： 暂无解析

相关内容