贪心算法之 活动安排（Java代码实现）

活动安排问题 -- 资源争夺

• 问题描述 - 设有 n 个活动的集合 A = {1, 2, ... , n}, 其中每个活动都要求使用同一资源，而在同一时间段内只有一个活动能使用资源 - 要求高效安排一系列争用公共资源的活动
• 问题本质 - 在所给活动活动集合中选出最大相容活动子集 X
• 实例： 多个部门申请占用一个资源

部门 | 物理 | 数学 | 化学 | 外语 | 生物 | 音乐 | 计算机

• | - | - | - | - | - | - | - | 起始时间 | 8 | 9 | 11 | 7 | 10 | 6 | 8 结束时间 | 9 | 10 | 12 | 10 | 12 | 8 | 11

1. 问题描述
   • 输入： n（问题规模）, si（开始时间），fi（终止时间）
   • 输出： count（存放活动总数）， xn（逻辑数组：活动被安排为 1，未被安排为 0）
   • 策略 - si （起始时间） × - Δt （活动时间） × - fi （结束时间）√ >显然s[i] 和 Δt 不能作为衡量标准，而f[i] 可以作为衡量标准
2. 算法实现
   • 预处理： fi 非递减序列
   • 贪心选择 - 最早完成的活动优先加入相容集合 x使剩余活动可安排时间段极大化，相容活动集最大 si >= fj or sj >= fi
3. 设计分析
   • 若输入的活动已就序 - 算法实现最大相容集时间： O(n)
   • 若给出的活动为就序 - 重排: O(nlogn)， 求最大相容集: O(n) - T(n) = O(nlogn) + O(n) = O(nlogn)
   • 算法中的3个数组和4个普通变量占用存储空间 - S(n) = O(3n) + O(4) = O(n)

	/**
	 * 数组需按非递减序列 f[1] <= f[2] <= ... <= f[n] 排列
	 * @param s 活动开始时间数组
	 * @param f 活动结束时间数组
	 * @param a 存放选择的活动
	 * @return 选择的活动个数
	 */
	public static int selector(int[] s, int[] f, boolean[] a) {
		int n = s.length - 1;
		a[1] = true;
		int j = 1;
		int count = 1;
		for (int i = 2; i <= n; i++) {
			if (s[i] >= f[j]) {
				a[i] = true;
				j = i;
				count ++;
			} else {
				a[i] = false;
			}
		}
		return count;
	}