UC知道数据结构的一个问题（会场排序）
来源：百度知道 编辑：UC知道 时间：2024/07/04 10:57:43
设有n个活动需要演讲会场，而在同一时间内会场只能分配给其中一个活动。如果用E表示活动集合，E={1,2,…, n},每个活动i使用会场有一个起止时间(Si，fj),其中Si< fj。如果两个活动i和j的时间段不相交，则称活动i和j是相容的，前后活动的时间边界重合不算相交。给定规模为10的问题实例E如下：
{(1,3),(0,5),(7,10),(6,7),(3,6),(8,9),(1,2),(11,12),(8,11),(10,13)}
1．给出以上问题的解及求解过程
2．设计一个求解“活动方案”的算法，使得在方案中安排的所有活动都是相容的且活动数目最多。
{(1,3),(0,5),(7,10),(6,7),(3,6),(8,9),(1,2),(11,12),(8,11),(10,13)}
1．给出以上问题的解及求解过程
2．设计一个求解“活动方案”的算法，使得在方案中安排的所有活动都是相容的且活动数目最多。
1。(1,2)(3,6)(6,7)(8,9)(11,12)，
-----求解过程：每次取可以安排的结束时间最小的活动。
2。算法很简单:
--1--将所有活动，按照“结束时间”排序，从小到大。
--2--取最前面的活动，作为下一个要安排的活动。当前时间记为其结束时间
--3--遍历所有活动，把开始时间小于当前时间的活动去掉。继续--2--，直到所有活动被安排或者去掉。
-------说明：算法细节还可以优化。