首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
admin
2019-10-08
57
问题
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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)。
(4)
选项
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个场地。
转载请注明原文地址:https://kaotiyun.com/show/xFCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和有关的图表,回答问题1至问题3。[说明]A公司决定为该市车站开发自动售票系统,系统的要求如下:1.乘客能按以下三步操作购票:选定目的地;投入钱币;获得一张票。2.当且仅当乘客选定目的地后,系统才接收投钱,每次投
阅读下列程序说明和C代码,将应填人(n)处的字句写在对应栏内。[程序5说明]下列文法可用来描述化学分子式的书写规则(例如,A12(CO3)3”Cu(OH)2):λ→β\βλβ→δ\δnδ→ξ\ξθ\(λ)其中
阅读以下说明和表,回答问题1~3问题。[说明]在学校中,存在以下关系:(a)一个系有若干学生,但一个学生只能在一个系;(b)一个学生可以选修多门课程,每门课程有若干学生选修;(c)每个学生所学的每门课程都有一个成绩。
阅读以下关于某订单管理系统的技术说明、部分UML类图及C++代码,将C++程序中(1)~(5)空缺处的语句填写完整。[说明]某订单管理系统的部分UML类图如图5-15所示。图5-15中,Product表示产品,Produc
需求分析是一个包括创建和维持系统需求文档所必需的一切活动的过程。一个通用的需求分析过程模型如图6-16所示,请从以下供选择的答案中选择合适的内容填写到图6-16中相应的位置中。[供选择的答案]A.用户需求和功能需求B.需求
图7-10中只有一个外部实体E1。使用[说明]中的词语,给出E1的名称。在进行系统分析与设计时,面向数据结构的设计方法(如Jackson方法)也被广泛应用。简要说明面向数据结构设计方法的基本思想及其适用场合。
阅读下列说明,回答问题1至问题3。【说明】请设计一个图书馆数据库,此数据库中对每个借阅者保存的读者记录包括:读者号、姓名、地址、性别、年龄、单位。对每本书存有:书号、书名、作者、出版社。对每本书被借出的书存有读者号、借出日期和应还日期。
[说明]公司IT部门决定开发一个计算机管理系统以记录期刊的传阅情况。期刊在公司内部传阅,员工可以要求加入传阅队列。图书室登记公司收到的期刊,交给名单中的第一名员工。员工应在三个工作日内完成阅读,员工阅读完毕后通知系统,系统提醒下一位阅读者取
关于软件著作权的说法中不正确的是(10)。
随机试题
A.羊水过多B.羊水过少C.AFP正常D.AFP降低E.以上都不是无脑儿
全球引起关注要求防治的主要热带寄生虫病是
A.ApoAⅠB.ApoCⅢC.ApoCⅡD.ApoDE.Apo(a)能抑制脂蛋白脂肪酶(LPL)的载脂蛋白是
男,45岁,因恶心、呕吐l周就诊,检查发现:贫血貌,血压195/110mmHg,血肌酐981μmol/L;肾脏B超:长轴7.8cm。最可能的诊断是
简述民事法律行为有效的实质要件。[湘潭大学2016年研]
下列建设工程项目进度控制措施中,属于经济措施的有()。
下列关于个人住房贷款的表述,错误的是()。[2014年11月真题]
汉武帝时期,采用了董仲舒“罢黜百家,独尊儒术”的建议,并颁布了推恩令。()
在Windows环境中,指定活动窗口的方法是()。
下列诗句中,与西安有关的有()。
最新回复
(
0
)