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

• 问题描述

• 设有 n 个活动的集合 A = {1, 2, ... , n}, 其中每个活动都要求使用同一资源，而在同一时间段内只有一个活动能使用资源

• 要求高效安排一系列争用公共资源的活动

• 问题本质

• 在所给活动活动集合中选出最大相容活动子集 X

• 实例： 多个部门申请占用一个资源

1. 问题描述

2. 输入： n（问题规模）, s[i]（开始时间），f[i]（终止时间）

3. 输出： count（存放活动总数）， x[n]（逻辑数组：活动被安排为 1，未被安排为 0）

4. 策略

5. s[i] （起始时间） ×

6. Δt （活动时间） ×

7. f[i] （结束时间）√

8. 显然 s[i] 和 Δt 不能作为衡量标准，而 f[i] 可以作为衡量标准

9. 算法实现

10. 预处理： f[i] 非递减序列

11. 贪心选择

12. 最早完成的活动优先加入相容集合 x

13. 使剩余活动可安排时间段极大化，相容活动集最大 s[i] >= f[j] or s[j] >= f[i]

14. 设计分析

15. 若输入的活动已就序

16. 算法实现最大相容集时间： O(n)

17. 若给出的活动为就序

18. 重排: O(nlogn)， 求最大相容集: O(n)

19. T(n) = O(nlogn) + O(n) = O(nlogn)

20. 算法中的 3 个数组和 4 个普通变量占用存储空间

21. 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;  }