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

活动安排问题 – 资源争夺

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

部门	物理	数学	化学	外语	生物	音乐	计算机
起始时间	8	9	11	7	10	6	8
结束时间	9	10	12	10	12	8	11

问题描述
- 输入： n（问题规模）, s[i]（开始时间），f[i]（终止时间）
- 输出： count（存放活动总数）， x[n]（逻辑数组：活动被安排为 1，未被安排为 0）
- 策略
  - s[i] （起始时间） ×
  - Δt （活动时间） ×
  - f[i] （结束时间）√
  显然s[i] 和 Δt 不能作为衡量标准，而f[i] 可以作为衡量标准
算法实现
- 预处理： f[i] 非递减序列
- 贪心选择
  - 最早完成的活动优先加入相容集合 x
使剩余活动可安排时间段极大化，相容活动集最大
s[i] >= f[j] or s[j] >= f[i]

设计分析

若输入的活动已就序
- 算法实现最大相容集时间： 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;
}