现需要申请一些场地举办一批活动,每个活动有开始时间和结束时间。在同一个场地,如果一个活动结束之前,另一个活动开始,即两个活动冲突。若活动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减去没有安排活动的场地数即可得到所用的最少场地数。
下表给出了n=11的活动集合,根据上述算法,得到最少的场地数为()。
A.4
B.5
C.6
D.7
延伸阅读
你可能感兴趣的试题
A.O(n2)
B.O(e2)
C.O(n+e)
D.O(n*e)
A.关键字被依次映射到地址编号连续的存储位置
B.关键字不同的元素被映射到相同的存储位置
C.关键字相同的元素被映射到不同的存储位置
D.关键字被映射到哈希表之外的位置
对下面的二叉树进行顺序存储(用数组MEM表示),已知结点A,B,C在MEM中对应元素的下标分别为1,2,3,那么结点D,E,F对应的数组元素下标为()。
A.4,5,6
B.4,7,10
C.6,7,8
D.6,7,14
A.2i+j-1
B.2i+j
C.2i+j+1
D.3i-j+1
A.入队列和出队列操作都不需要遍历链表
B.入队列和出队列操作都需要遍历链表
C.入队列操作需要遍历链表而出队列操作不需要
D.入队列操作不需要遍历链表而出队列操作需要
A.Data Extraction
B.OLAP
C.OLTP
D.ETL
给定教师关系Teacher(T_no,T_name,Dept_name,Tel),其中属性T_no,T_name,Dept_name和Tel的含义分别为教师号,教师姓名,学院名和电话号码。用SQL创建一个“给定学院名求该学院的教师数”的函数如下:
A.returns integer
B.returns d_count integer
C.declare integer
D.declare d_count integer
热门相关试卷
最新相关试卷