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

刺骨的言语ヽ痛彻心扉 2023-02-09 14:28 16阅读 0赞

# 活动安排问题 – 资源争夺 #

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

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