和 Union具体化并付诸实现。 §2作业排序问题 ●活动安排问题 我们首先从活动安排这一简单课题入手。该问题要求高效地安排 系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题:已知n个活动E={1,2,…,n}要求使用同一资源,第k 个活动要求的开始和结束时间为s,f,其中s<f,k=1,2,…,n 活动k与活动j称为相容的如果s>f或者s>f。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排,好给后面的活动安排留出更多的空间,从而达到安排 最多活动的目标。据此,贪心准则应当是:在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中,将各项活动的开始时间和结 束时间分别用两个数组s和f存储,并使得数组中元素的顺序按结束 时间非减排列:f1≤f,≤…≤fn 活动安排贪心算法伪代码 Greedy Action(s,f,n)∥lln]、红ln]分别代表n项活动的起始 时间和结束时间,并且满足f1≤2]…≤fn l; solution={1};∥解向量初始化为空集 for i from 2 to n do和 Union 具体化并付诸实现。 §2 作业排序问题 z 活动安排问题 我们首先从活动安排这一简单课题入手。该问题要求高效地安排 一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题：已知 n 个活动 E={1, 2, … ,n}要求使用同一资源，第 k 个活动要求的开始和结束时间为 sk, fk, 其中 sk< fk, k=1, 2, … , n . 活动 k 与活动 j 称为相容的如果 sk> fj或者 sj> fk。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排 最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结 束时间分别用两个数组 s 和 f 存储，并使得数组中元素的顺序按结束 时间非减排列：f1≤ f2≤…≤ fn。 活动安排贪心算法伪代码 GreedyAction(s, f，n) // s[1:n]、f[1:n]分别代表 n 项活动的起始 //时间和结束时间, 并且满足 f[1]≤ f[2]≤…≤ f[n] j=1; solution={1}; //解向量初始化为空集 for i from 2 to n do