首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
admin
2019-10-08
56
问题
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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~4,将解答填入对应的解答栏内。[说明]假设二叉树采用链式存储方式存储,编写一个后序遍历二叉树的非递归方式。Voidpostorder(btree*B){btree*stack[m0
转换图中缺少哪三条数据流?请指明每条数据流的名称、起点和终点。在过程启动表中,d,e处应填什么?请分别用4位二进制码表示。
请将【算法2-1】和【算法2-2】中(1)~(7)处补充完整。请从下面的选项中选择相应的判断逻辑填补【算法2-1】中的“判断条件1”至“判断条件3”。注意,若“判断条件2”的逻辑判断结果为假,就无需对“判断条件3”进行判断。(a)字符是括号(b)字
在UML中,用例代表一个完整的功能,如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征,并指出用例图中(1)~(3)处表示的内容。UML采用5个互联的视图来描述软件系统的体系结构,即用例视图(Use-caseView)、设计视图(D
利用存在的依赖关系构造一个图书馆的对象模型。画出上一问中使用的图书馆程序的层次结构图。
阅读以下说明和数据流图,回答问题1~3问题。[说明]研究生招生系统旨在用计算机对学校的研究生招生事务进行管理。研究生招生可分为报名阶段、考试阶段和录取阶段。招生报考前,招生处要进行考前准备工作,如统计招生导师、考试科目以及制定报考专业标准代码
阅读下列说明和有关图表,回答问题。【说明】(1)这是一个图书馆支持系统。(2)图书馆应用系统可以将图书和杂志借给借书者,这些借书者已经在系统中注册了,图书和杂志也已经注册过了。(3)图书馆负责新书的购买,一本流行图书会多买几
在程序流程图(见图6-21)中,若要某个房间I被选中,则需要满足什么条件?如果等级为r的房间每人每天的住宿费为RATE(r),其中RATE为数组,则为使该算法在输出每个候选的房间号RM(J)后,再输出这批散客每天所需的总住宿费DAYRENT(J),在程
识别关联的多重度是面向对象建模过程中的一个重要步骤。请根据说明中给出的描述,将如图6-18所示中(1)~(6)空缺处的内容填写完整。现需了解十大最畅销(借出次数最多)图书或唱碟。为此引入类TemPopulate以存储所有十大畅销图书或CD的名称及其被借
In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups
随机试题
男性,49岁,体检发现右上肺有大小约3.5cm×2.5cm结节状界限不清病灶,疑为肿瘤。在超声引导下作肿物穿刺活检。病理报告为结核,病灶中有明显坏死及结核性肉芽肿形成,此种坏死是
男,60岁。因胃溃疡合并多次大出血,行胃大部切除术。该病人术后5天出现胃出血,最可能的原因是
向云龙电器有限责任公司投资,最多投资_________。与宏达销售有限公司共同建一合伙企业,最多可投资_________。
张山和王海二人因合同纠纷发生争议,诉至法院。法院判决张山赔偿王海20万元。判决生效后,张山未履行判决。王海隧向法院申请强制执行。在执行过程中,张山突然心脏病发死亡,留有遗产一套房屋。张山的唯一法定继承人张小山不愿继承张山的遗产。法院应该作出下列哪项处理?(
在股份有限公司的发起设立中,发起人应当承担的责任是:()
政府部门审查房地产项目是否允许转让的重要指标是()。
背景资料某公路工程完工后,项目经理部及时组织人员编造了工程技术总结。技术总结的内容有工程概况、“新技术、新工艺、新材料、新设备”的推广应用情况。问题:请补充技术总结的内容。
为适应产业结构调整升级的需要,某企业计划裁员10%,并将四个污染严重的车间进行停产。这四个车间的人数正好占该企业总人数的10%。计划实施后,上述四个车间停产,整个企业实际减员5%。此过程中,该企业内部人员有所调整,但整个企业只有减员,没有增员。根据以上信息
点M(2,1,一1)到直线L:的距离为().
Onesummernight,onmywayhomefromworkIdecidedtoseeamovie.Iknewthetheatrewouldbeair-conditionedandIcouldn’t
最新回复
(
0
)