活动安排问题

问题描述

• 设有n个活动的集合E={1, 2, 3, …, n}，其中每个活动都要求使用同一资源，如演讲会场的，而在同一时间内只有一个活动能使用这一资源，每个活动i都有一个要求使用该资源的起始时间s_i和一个结束时间f_i，且s_i<f_i，如果选择了活动i，则它在半开时间区间[s_i,f_i）内占用资源，若区间[s_i,f_i）与区间[s_j,f_j）不相交，则称活动i与活动j是相容的，也就是说，当s_i>=f_j或s_j>=f_i时，活动i与活动j相容，活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

代码实现

public class GreedySelector {

    public static void main(String[] args) {
        Integer[] s = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
        Integer[] f = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
        int n = s.length;
        boolean[] A = new boolean[n];
        GreedySelector(n, s, f, A);
        for (int i = 0; i < n; i++) {
            System.out.println("i=" + i + ":" + A[i]);
        }
    }

    public static <T extends Comparable<T>> void GreedySelector(int n, T[] s, T[] f, boolean[] A) {
        A[0] = true;
        int j = 0;
        for (int i = 1; i < n; i++) {
            if (s[i].compareTo(f[j]) >= 0) {
                A[i] = true;
                j = i;
            } else {
                A[i] = false;
            }
        }
    }
}

• GreedySelector(int n, T[] s, T[] f, boolean[] A)：计算活动安排问题，由于输入的活动是按其结束时间的非减序排列的，所以该算法每次总是选择具有最早完成时间的相容活动加入集合A中，直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间，也就是说，该算法的贪心选择的意义是使剩余的可安排时间留下尽可能多的相容活动。
  • int n：活动的数量。
  • T[] s：活动开始时间序列。
  • T[] f：活动结束时间序列，非降序排列。
  • boolean[] A：活动是否被选择。