首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
admin
2019-10-08
41
问题
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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://jikaoti.com/ti/DmG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
如果将上述应用的数据库设计成如下关系模式;RS(A#,A1,A2,A3,B#,B1,B2,D1),请指出该关系模式的候选键。如果将上述应用的数据库设计为如下三个关系模式:R1(A#,A1,A2,A3)R2(B#,B1,B2)
阅读以下说明和Java码,将应填入(n)处的字名写在的对应栏内。[说明]编写一个完整的JavaApplet程序使用复数类Complex验证两个复数1+2i和3+4i相加产生一个新的复数4+6i。复数类Complex必须满足如下要求
阅读下列程序说明和程序段,将应填人(n)处的字句写在对应栏内。[说明]下面是一个Applet程序,其功能是有2个按钮,分别为First和Second,以及一个Label控件。要求点击First时则能在Label中显示出Command:Fi
阅读以下说明,回答问题1至问题3,将解答写在对应栏内。【说明】有如下关系数据库:S(SNO,SN,STATUS,CITY)P(PNO,PN,COLORS,WEIGHT)J(JNO,JN,CITY)SPJ(SN
请认真阅读以下关于电子政务信息整合的叙述,根据要求回答问题1~问题4。[说明]公共服务、社会监督和宏观调控是我国政府的3个主要职能。实施电子政务建设,可以改善政府的公共服务质量,提高社会监管的效率和准确性,加强宏观经济调控的科学性。
阅读下列说明,回答问题1至问题3。【说明】请设计一个图书馆数据库,此数据库中对每个借阅者保存的读者记录包括:读者号、姓名、地址、性别、年龄、单位。对每本书存有:书号、书名、作者、出版社。对每本书被借出的书存有读者号、借出日期和应还日期。
阅读以下技术说明及Java代码,将Java程序中(1)~(5)空缺处的语句填写完整。[说明]在一公文处理系统中,开发者定义了一个公文类OfficeDoc,其中定义了公文具有的属性和处理公文的相应方法。当公文件的内容或状态发生变化时,关注此
In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups
In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups
某软件公司将与他人共同开发、共同享有著作权的软件,作为自己单独开发的软件向国家软件著作权登记机构申请软件著作权登记。其他软件著作权人发现后,可以依法追究该软件公司的(21)。
随机试题
北宋时,钧窑的白瓷最有名气。()
丝网印刷的特点是墨层厚,有浮凸感,制版简便、成本低。
属于胆色素的物质有
某建材厂设计能力为年生产某型号预制构件7200件,每件售价5000元,该厂固定成本680万元,每件产品变动成本为3000元,则该厂的盈亏平衡产量为()件。
2008年1月1日,该塑钢机的最低租赁付款额为( )元。根据上述3确定的未确认融资费用分摊率,公司2008年应分摊融资费用为( )元。
注册会计师对期初余额审计时,若前任注册会计师出具了保留意见的审计报告,则注册会计师也仍应在审计报告中反映。()
张磊发现,在检查自己昨晚的试卷和作业时,很难发现其中的错误,但帮别的同学检查时,却很容易发现,这主要是由于()的影响。
置将法
如图3所示,在直角△ABC中,∠ACB=90°,DE过点C且平行于AB,若∠BCE=35°,则∠A的度数为()。
Inthe19thcentury,itwascommontohearpeopleinEuropeandAmericasaythattheresourcesoftheseawereunlimited.Forex
最新回复
(
0
)