首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动A从1时间开始,5时间结束,活动B从5时间开始,8时间结束,则活动A和B不冲突。现要计算n个活动需要的最少场地数。求解该
admin
2019-10-08
42
问题
现需要申请,些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读以下说明和VisualBasic代码,将相应文字填入(n)处,并写在对应栏内。[说明]以下VisualBasic代码实现了对位图(BMP)进行旋转显示。以下程序共实现了对BMP位图图形进行180°旋转、90°旋转(顺时针)、90°旋转
阅读下列函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。【说明】假定用一个整型数组表示一个长整数,数组的每个元素存储长整数的一位数字,则实际的长整数m表示为:m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]
根据题意,给出类“传阅记录”的主要属性。根据题意,将图9-5中的(1)~(5)处补充完整。
阅读下列C++程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】[程序6说明]单源最短路径的分支限界算法。constintMAXNUM=29999;#include<iostream>#include<vector>#include
阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】用克鲁斯卡尔算法求解给定图的最小生成树。#include<stdio.h>#include<stdlib.h>#defineMAXN30
对于教学数据库的三个基本表S(S#,SNAME,AGE,SEX),SLLS#,C#,GRADE),C(C#,CNAME,TEACHER)。现根据查询条件填充下面SQL语句空白的部分。1.检索LIU老师所授课程的课程号和课程名。2.检索至少
假设当前该旅馆各个房间的情况见表3。当输入M=4,R=0时,该算法的输出是什么?如果限制该算法最多输出K个可供选择的房间号,则在流程图1的。所指的判断框应改成什么处理?
(37)是指把数据以及操作数据的相关方法组合在同一个单元中,使我们可以把类作为软件中的基本复用单元,提高其内聚度,降低其耦合度。面向对象中的(38)机制是对现实世界中遗传现象的模拟,通过该机制,基类的属性和方法被遗传给派生类。
In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups
随机试题
根据中共中央办公厅、国务院办公厅印发的《关于全面加强和改进新时代学校美育工作的意见》,下列说法错误的是()。
琥珀酸氧化呼吸链的成分不包括
关于过期妊娠以下不正确的选项是
下列哪项不是大量不保留灌肠的适应证( )
以下有关需求法则说法错误的是( )。
对产品质量监督部门依法进行的产品质量监督检查,生产者、销售者()。
下列关于成本的表述中,不正确的是()。
积累基金是指国民收入中用作追加生产资金的部分,主要包括:扩大再生产基金,如建工厂、修铁路、开垦土地、兴建水利等;非生产性基本建设基金,如修建学校、医院、体育场馆以及国家行政、国防部门的基本建设等;社会后备资金,如应付战争、自然灾害等突发性事件的物质储备等。
foreignizingmethod
下面是关于常用图像文件的叙述,其中错误的是______。
最新回复
(
0
)