活动安排算法

问题描述

设有n个活动，每个活动要求使用统一资源，每个活动i都有起始时间s和一个结束时间f，活动1执行完成后活动2也可以完全执行，则活动1与活动2相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。活动结束时间以升序排列。

算法分析

1.活动安排问题可以用贪心算法求解，从贪心算法的思想出发，总是作出当前最好的选择，并不需要从整体最优考虑，完成的是局部最优选择，整体最优解可以通过一系列局部最优的选择当然活动安排问题用贪心算法求解则是最优选择。

2.基本思路

一、建立数学模型来描述问题。

二、把求解的问题分成若干个子问题。

三、对每一子问题求解，得到子问题的局部最优解。

四、把子问题的解局部最优解合成原来解问题的一个解。

java 源代码：

import java.util.Scanner;

public class Greedy {
    public static void greedySelector(int []s,int[] t,boolean []a){
        a[0] = true;
        int j=0;
        int count=1;
        for (int i = 1; i <=s.length-1; i++) {
            if(s[i]>=t[j]){
                a[i]=true;
                j=i;
                count++;
            }
            else a[i]=false;
        }
        System.out.println("活动个数：");
        System.out.println(count);
        System.out.println("活动顺序：");
        for (int i = 0; i < a.length; i++) {
            if (a[i]==true){
                System.out.print(i+",");
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);      //活动以结束时间升序排列
        System.out.println("输入活动个数：");
        int a = sc.nextInt();
        int[] f = new int[a];
        int[] g = new int[a];
        System.out.println("依次输入全部活动的开始时间：");
        for (int i = 0; i < a; i++) {
            f[i] = sc.nextInt();
        }
        System.out.println("依次输入全部活动的结束时间：");
        for (int i = 0; i < a; i++) {
            g[i] = sc.nextInt();
        }
        boolean [] b = new boolean[a];
        Greedy test = new Greedy();
        test.greedySelector(f,g,b);
    }
}

复杂度分析

贪心算法不是很复杂的算法，当输入的活动已按结束时间的升序排列，算法只需*O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未非升序排列，可以用O(nlogn)*的时间重排。