首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
admin
2019-10-08
38
问题
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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减去没有安排活动的场地数即可得到所用的最少场地数算法首先采用了快速排序算法进行排序,其算法设计策略是_______(1);后面步骤采用的算法设计策略是_______(2)。整个算法的时间复杂度是_______(3)。下表给出了n=11的活动集合,根据上述算法,得到最少的场地数为_______(4)。
(1)
选项
A、分治
B、动态规划
C、贪心
D、回溯
答案
A
解析
转载请注明原文地址:https://kaotiyun.com/show/3FCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
数据流图1(网络故障检测系统顶层图)中的A和B分别表示什么?将数据流图3(加工4的细化图)中的数据流补充完整,并指明加工名称、数据流的方向(输入/输出)和数据流名称。
数据流图1(网络故障检测系统顶层图)中的A和B分别表示什么?数据流图2(网络故障检测系统第0层DFD图)中的数据存储“配置信息”会影响图中的哪些加工?
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】[程序6说明]单源最短路径的分支限界算法。constintMAXNUM=29999;#include<iostream>#include<vector>#include
假设当前该旅馆各个房间的情况见表3。当输入M=4,R=0时,该算法的输出是什么?如果限制该算法最多输出K个可供选择的房间号,则在流程图1的。所指的判断框应改成什么处理?
阅读以下说明和C++码,填入(n)处。[说明]下面代码实现类A、B、C、D的继承定义和应用。仔细阅读[代码5-1],在(n)处写出正确的运行结果。[代码5-1]#include<iostream.h>classA
阅读以下说明和c++代码,将应填入(n)处的字句写在对应栏内。【说明】现要编写一个画矩形的程序,目前有两个画图程序:DP1和DP2,DP1用函数draw_a_line(x1,y1,x2,y2)画一条直线,DF2则用drawline(x1
阅读以下说明和图,回答问题1至问题3,将解答写在对应栏内。【说明】某教学管理系统的用户是教学管理人员、教师和学生。系统主要提供学生选课管理和学生成绩管理两方面的功能。(1)学生选修课管理主要功能是管理新学期开始时,学生对选
软件设计的主要任务是设计软件的结构、过程和模块,其中软件结构设计的主要任务是要确定(11)。
小张在M公司担任程序员,他执行本公司工作任务,独立完成了某应用程序的开发和设计,那么该应用程序的软件著作权应当归属______享有。
软件著作权受法律保护的期限是______。一旦保护期限届满,权利自行终止,成为社会公众可以自由使用的知识。
随机试题
有预定目的,不需要意志努力的注意是【】
患者,男,27岁。走路时被摩托车从后方撞击右膝,出现右髋剧痛,患肢呈外展、外旋和屈曲畸形位弹性固定,抬动时患肢发生肌肉痉挛。应诊断为
环糊精包合物在药剂学中常用于( )。
甲乙两国于1996年签订投资保护条约,该条约至今有效。2004年甲国政府依本国立法机构于2003年通过的一项法律,取消了乙国公民在甲国的某些投资优惠,而这些优惠恰恰是甲国按照前述条约应给予乙国公民的。针对甲国的上述作法,根据国际法的有关规则,下列哪一项判断
建设工程项目设计阶段有初步设计、技术设计和施工图设计,其顺序为______。
根据《公司债券受托管理人执业行为准则》的规定,公司债券受托管理人应当向市场公告临时受托管理事务报告的情形不包括()。[2016年5月真题]
长城股份有限公司(以下简称长城公司)2013年度实现税前会计利润2500万元,采用资产负债表债务法核算所得税,适用的所得税税率为25%,按净利润的10%计提盈余公积。长城公司2013年度的汇算清缴于2014年4月15日前完成,财务会计报告于2014年4月2
下列用地中,不属于临时建设用地的是()。
法律工作者为社区居民提供法律咨询,定期进行法律宣传等,这体现社区_________建设。
17周岁的高中生甲继承其父价值15万元的劳力士手表一块。后未经其母同意将该表以13万元出卖给乙,因甲长得高大魁梧,举止言谈较老成,乙误信其已成年,遂将此表买下。二日后,乙又将此表以13.8万元转卖给不知情的丙。甲母获悉此事后,向乙交涉,认为甲、乙之间的买卖
最新回复
(
0
)