首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
admin
2019-10-08
37
问题
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在UML中,用例代表一个完整的功能,如与角色通信、进行计算或在系统内工作等。请简要说明用例具有哪些的特征,并指出用例图中(1)~(3)处表示的内容。UML采用5个互联的视图来描述软件系统的体系结构,即用例视图(Use-caseView)、设计视图(D
阅读以下说明,回答问题1~2,将解答填入对应的解答栏内。[说明]设某商业集团数据库中三个实体集。一是“仓库”实体集,属性有仓库号、仓库名和地址等;二是“商店”实体集,属性有商店号、商店名、地址等;三是“商品”实体集,属性有商品号、商品名、单价。
对文法G进行改写,然后对每个非终结符写出不带回溯的递归于程序。经改写后的文法是否是LL(1)的?指出它的预测分析表中(1)~(3)处的内容。
阅读以下说明和图,回答问题1至问题3,将解答写在对应栏内。【说明】某教学管理系统的用户是教学管理人员、教师和学生。系统主要提供学生选课管理和学生成绩管理两方面的功能。(1)学生选修课管理主要功能是管理新学期开始时,学生对选
阅读下列程序说明,将应填入(n)处的字句写在答卷纸的对应栏内。【程序说明】对于一个公司的雇员来说,无非有3种:普通雇员、管理人员和主管。这些雇员有共同的数据:名字、每小时的工资,也有一些共同的操作:数据成员初始化、读雇员的数据成员及计算雇员
企业信息整合、共享需要一个代表企业身份的信息,该信息应该具有唯一性和易管理性,上述表格中信息项(1)代表企业身份最合适。该市政府各委、办、局已经分别投资立项建设了业务自动化系统和信息管理系统,仅从保护投资的角度出发,也难以一下子按企业基础数据集
请将图4-15中各实体之间的联系补充完整。如果将商品信息只存储在中心数据库中,与在各POS机上存储其备份相比,从前台销售效率和更新商品库两方面论述各自的优缺点(不超过300字)。
阅读下列说明,根据要求回答问题1~问题3。[说明]某企事业单位资料室需要建立一个图书管理系统,初步的需求分析结果如下:(1)资料室有图书管理员若干名,他们负责已购入图书的编目和借还工作,每名图书管理员的信息包括工号和姓名;(
In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups
随机试题
能代表心室肌前负荷的指标是
属于硫脲类抗甲状腺药物的是
最有可能引起奶牛创伤性心包炎的异物是()
承担完善职业资格制度,拟定专业技术人员管理和继续教育政策、社会保障体系建设等职能的部门是()。
设力F在x轴上的投影为F,则该力在与x轴共面的任一轴上的投影:
工作流程图用图的形式反映一个组织系统中各项工作之问的逻辑关系,它可用来描述( )。
财政部门管理会计电算化的基本任务是()。
甲公司是一个汽车挡风玻璃批发商,为5家汽车制造商提供挡风玻璃。该公司总经理为了降低与存货有关的总成本,请你帮助他确定最佳的采购批量。有关资料如下:(1)挡风玻璃的单位进货成本为1300元。(2)全年需求预计为9900块。(3)每次订货发出与处理订单的
根据以下资料。回答下列问题题。2012年,长春市汽车工业完成产值4888.5亿元,比上年增长16.5%;完成工业增加值1104.7亿元。2012年1-11月,汽车工业实现主营业务收入4954.2亿元,比上年同期增长11.6%;实现利润总
Bycuttingoutthemiddlemanandbookingyourownflights,youcansaveupto40percentofthecostofaholiday.Ifyoucomp
最新回复
(
0
)