活动安排问题—贪心算法—java实现

目标

在所给的活动集合中选出一个最大的相容活动子集和。
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源（如一个阶梯教室等），而在
同一时间内只有一个活动能使用这一资源。

1、每个活动i都有一个要求使用该资源的起始时间startTime和一个结束时间endTime，
且0<=startTime < endTime。
2、如果选择了活动i，则它在半开时间区间[startTime, endTime)内占用资源。
3、若区间[[startTimei, endTimei)与区间[[startTimej, endTimej)不相交，则称活动i与
活动j是相容的。
也就是说，当startTimei ≥ endTimej 或 endTimei ≥ startTimej时，活动i与活动j相容。

贪心选择

选择这样一个活动：选出它后，剩下的资源应能被尽量多的其他任务所用
直觉告诉我们，应该选择E中最早结束的活动，因为它剩下的资源可供它之后尽量
多的活动使用。这个选择的正确性可以证明，有兴趣的同学可以查查看。
我的做法是将活动定义为一个类，属性有开始时间—startTime、结束时间—endtTime、
活动名称—name，类中还实现了对活动排序的接口：

public static class ACs implements Comparable<ACs>{

        private int startTime;//开始时间
        private int endTime;//结束时间
        private String name;//活动名称

        public ACs(int startTime, int endTime,String name) {
            super();
            this.startTime = startTime;
            this.endTime = endTime;
            this.name = name;
        }

        public ACs() {
            super();
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getStartTime() {
            return startTime;
        }

        public void setStartTime(int startTime) {
            this.startTime = startTime;
        }

        public int getEndTime() {
            return endTime;
        }

        public void setEndTime(int endTime)**
         * 实现对活动排序的接口
         */
        @Override
        public int compareTo(ACs o) {
            // TODO Auto-generated method stub
            return this.endTime - o.endTime;
        }

    }

核心代码

    private static void GreedySeletor(int n,ACs[] s,boolean[] a) {
        a[1] = true;
        int j = 1;
        for(int i = 2;i<=n;i++) {
            if(s[i].getStartTime() >= s[j].getEndTime()) {
                a[i] = true;
                j = i;
            }
            else {
                a[i] = false;
            }
        }
    }

完整代码

package activities;

import java.util.Arrays;

public class Act {
    private static boolean[] x;
    private static int[] y;

    public static class ACs implements Comparable<ACs>{

        private int startTime;//开始时间
        private int endTime;//结束时间
        private String name;//活动名称

        public ACs(int startTime, int endTime,String name) {
            super();
            this.startTime = startTime;
            this.endTime = endTime;
            this.name = name;
        }

        public ACs() {
            super();
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getStartTime() {
            return startTime;
        }

        public void setStartTime(int startTime) {
            this.startTime = startTime;
        }

        public int getEndTime() {
            return endTime;
        }

        public void setEndTime(int endTime) {
            this.endTime = endTime;
        }

        /**
         * 实现对活动排序的接口
         */
        @Override
        public int compareTo(ACs o) {
            // TODO Auto-generated method stub
            return this.endTime - o.endTime;
        }

    }

    private static void GreedySeletor(int n,ACs[] s,boolean[] a) {
        a[1] = true;
        int j = 1;
        for(int i = 2;i<=n;i++) {
            if(s[i].getStartTime() >= s[j].getEndTime()) {
                a[i] = true;
                j = i;
            }
            else {
                a[i] = false;
            }
        }
    }



    public static void main(String[] args) {
        // TODO Auto-generated method stub
        x = new boolean[7];
        x[0] = false;
        ACs a0 = new ACs();
        ACs a1 = new ACs(1,4,"活动一");
        ACs a2 = new ACs(3,5,"活动二");
        ACs a3 = new ACs(0,6,"活动三");
        ACs a4 = new ACs(3,8,"活动四");
        ACs a5 = new ACs(5,7,"活动五");
        ACs a6 = new ACs(5,9,"活动六");


        ACs[] A = new ACs[7];
        A[0] = a0;
        A[1] = a1;
        A[2] = a2;
        A[3] = a3;
        A[4] = a4;
        A[5] = a5;
        A[6] = a6;

        Arrays.sort(A);

        GreedySeletor(6,A,x);

        for(int i = 1;i<=6;i++) {
            if(x[i] == true) {
                System.out.println(A[i].getName());
            }
        }
    }
}

运行