8、实验七活动安排

实验内容

设有n个活动的集合E={1, 2, … n}, 其中每个活动都要求使用同一资源且在同一时间内只有一个活动能使用这一资源。要求根据下述两种贪心准则，给出活动集合中最大的相容活动子集合。

(1)使用“将结束时间早的活动尽量先排”作为贪心准则。
(2)使用“将最少占用时间的活动尽量先排”作为贪心准则。

解题思路

将活动按照结束时间进行从小到大排序。然后用i代表第i个活动，s[i]代表第i个活动开始时间，f[i]代表第i个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续下一活动与集合A中活动的相容性。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置。

源代码

package g活动安排问题;

import java.util.Scanner;

/**
 * @author Draco
 * @see "将结束时间早的活动尽量先排"作为贪心准则
 * @version 1.0
 * @date-time 2020-06-01 - 下午12:19:16
 */
public class Plan {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.print("请输入活动的个数：");
		int num = scanner.nextInt();
		// 创建开始数组和结束数组
		int[] start = new int[num];
		int[] end = new int[num];
		System.out.println("请分别输入开始时间s[i]和结束时间f[i]：");
		for (int i = 0; i < num; i++) {
			System.out.println();
			System.out.print("s[" + (i + 1) + "]=");
			int begin = scanner.nextInt();
			System.out.print("f[" + (i + 1) + "]=");
			int end1 = scanner.nextInt();
			start[i] = begin;
			end[i] = end1;
		}

		// 创建一个数组存储是否安排活动
		boolean[] arrange = new boolean[num + 1];
		// 遍历数组，判断那些需要安排，安排的规则是按照顺序，没有相交的部分就安排
		arrange[0] = true;
		for (int i = 1, j = 0; i < start.length; i++) {
			// 如果前一个的结束时间比后一个的开始时间小。则安排下去
			if (end[j] < start[i]) {// 符合要求
				arrange[i] = true;
				j = i;// 如果成立，则j就是下一个作为参考的时间
			} else {
				arrange[i] = false;
			}
		}
		System.out.println();
		System.out.println("按结束时间非递减顺序排列如下：");
		System.out.println("序号\t开始时间\t结束时间");
		System.out.println("--------------------");

		int[] Index = new int[end.length];
		Index = Plan.Arraysort(end);

		for (int i = 0; i < num; i++) {
			System.out.print((i + 1) + "\t");
			// 对应下标
			System.out.print(start[Index[i]] + "\t");
			System.out.println(end[i]);
		}
		System.out.println("--------------------");

		System.out.println("安排的活动序号依次是：");
		for (int i = 0; i < arrange.length; i++) {
			if (arrange[i] == true) {
				System.out.println((i + 1));
			}
		}
	}

	public static int[] Arraysort(int[] arr) {
		int temp;
		int index;
		int k = arr.length;
		int[] Index = new int[k];
		for (int i = 0; i < k; i++) {
			Index[i] = i;
		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;

					index = Index[j];
					Index[j] = Index[j + 1];
					Index[j + 1] = index;
				}
			}
		}
		return Index;
	}
}

package g活动安排问题;

import java.util.Scanner;

/**
 * @author Draco
 * @see "将最少占用时间的活动尽量先排"作为贪心准则
 * @version 1.0
 * @date-time 2020-06-01 - 下午12:22:46
 */
public class Plan1 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.print("请输入活动的个数：");
		int num = scanner.nextInt();
		// 创建开始数组和结束数组
		int[] start = new int[num];
		int[] end = new int[num];
		System.out.println("请分别输入开始时间s[i]和结束时间f[i]：");
		for (int i = 0; i < num; i++) {
			System.out.println();
			System.out.print("s[" + (i + 1) + "]=");
			int begin = scanner.nextInt();
			System.out.print("f[" + (i + 1) + "]=");
			int end1 = scanner.nextInt();
			start[i] = begin;
			end[i] = end1;
		}

		// 创建一个数组存储是否安排活动
		boolean[] arrange = new boolean[num + 1];
		// 创建一个数组存储活动所需的时间
		int[] spend = new int[num];
		// 给时间数组赋值
		for (int i = 0; i < num; i++) {
			spend[i] = end[i] - start[i];
		}

		System.out.println();
		System.out.println("按活动所需时间非递减顺序排列如下：");
		System.out.println("序号\t开始时间\t结束时间\t活动所需时间");
		System.out.println("---------------------------");

		int[] Index = new int[spend.length];
		Index = Plan1.Arraysort(spend);

		for (int i = 0; i < num; i++) {
			System.out.print((i + 1) + "\t");
			// 对应下标
			System.out.print(start[Index[i]] + "\t");
			System.out.print(end[Index[i]] + "\t");
			System.out.println(spend[i]);
		}
		System.out.println("---------------------------");

		// 遍历数组，判断那些需要安排
		arrange[0] = true;
		for (int i = 1, j = 0; i < start.length; i++) {
			// 如果前一个的结束时间比后一个的开始时间小。则安排下去
			if (end[j] < start[Index[i]]) {// 符合要求
				arrange[i] = true;
				j = i;// 如果成立，则j就是下一个作为参考的时间
			} else {
				arrange[i] = false;
			}
		}

		System.out.println("安排的活动序号依次是：");
		for (int i = 0; i < arrange.length; i++) {
			if (arrange[i] == true) {
				System.out.println((i + 1));
			}
		}
	}

	public static int[] Arraysort(int[] arr) {
		int temp;
		int index;
		int k = arr.length;
		int[] Index = new int[k];
		for (int i = 0; i < k; i++) {
			Index[i] = i;
		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;

					index = Index[j];
					Index[j] = Index[j + 1];
					Index[j + 1] = index;
				}
			}
		}
		return Index;
	}
}

运行截图

1、“将结束时间早的活动尽量先排”作为贪心准则

2、“将最少占用时间的活动先排”作为贪心准则

问题描述：活动安排问题--贪心算法

    有11项考试要安排，每项活动 i 的开始时间为  (start)，结束时间为 (finish)
    问在规定的时间内最多可安排多少项活动？

具体实现代码及详细注释

public class ActivityArrange {

        /*
        解决方案代码：
        i    表示 第i个活动
        s[i] 表示 第i个活动的开始时间
        f[i] 表示 第i个活动的结束时间
        a[i] 是否选择安排第i个活动（true代表是，false代表否）
        */
        public static void greedySelector(int[] s, int[] f, boolean[] a)
        {
            a[1] = true;		// 选择安排活动1
            int j = 1;		// 记录最近一次的活动序号
            int count = 1;		// 总的可以安排的活动数

            int n = s.length - 1;
            for(int i=2; i<=n; i++)	// 依次检查其余每一项活动与已选择的活动的相容性
            {
                if(s[i] >= f[j])	// 如果第i项活动相容
                {
                    a[i] = true;	// 选择安排第i项活动
                    j = i;		// 记录最近一次的活动序号
                    count++;	// 总的可以安排的活动数加1
                }
                else			// 如果不相容
                    a[i] = false;	// 选择不安排第i项活动
            }

            // 打印 活动安排情况，安排的数量
            for (int i=1; i<a.length; i++)
                System.out.println("A" + i + " = " + a[i]);
            System.out.println("总的活动数量 = " + count);
        }

        public static void main(String[] args)
        {
            // 定义11项活动的开始时间，结束时间（按升序排序）
            int[] s = {0,1,3,0,5,3,5,6, 8, 8, 2, 12};// s[0]不用
            int[] f = {0,4,5,6,7,8,9,10,11,12,13,14};// f[0]不用
            boolean[] a = new boolean[12];// a[0]不用

            // 调用贪心算法 安排活动 并 计算最大可安排数量
            greedySelector(s, f, a);

        }
}

又是好久没更，最近一直在忙杂七杂八的，更一个算法作业吧。

问题

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。

或者

设有n个活动的集合E＝{1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si＜fi。如果选择了活动i，则它在半开时间区间[si ，fi )内占用资源。若区间[si ，fi )与区间[sj，fj )不相交，则称活动i与活动j是相容的。当 si ≥ fj 或 sj ≥ fi 时，活动i与活动j相容。
活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。

分析

开始最早的方案基本不用考虑，这里不解释。

我最初的方法是先找时间间隔最短的，这样就可以留出足够多的时间去举办别的活动。
但是我忽略了一点，这样分割出来的很有可能是不间隔的两段时间段。按照这个规则选取活动的话，取一两次之后时间可能就被分割成不同大小的不连续小段，这样肯定不能再用了。

那我们就让剩余的时间段连续起来，还要最大，那么我们就选择结束时间最早的，这样留出来的是整块的时间还挺大。

代码

/**
 * @ClassName ActivityArrangement
 * @Description 活动安排问题 贪心算法 不考虑整体最优而专注局部最优解
 *
 *设有n个活动的集合E＝{1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，
 * 而在同一时间内只有一个活动能使用这一资源。
 * 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si＜fi。
 * 如果选择了活动i，则它在半开时间区间[si ，fi )内占用资源。若区间[si ，fi )与区间[sj，fj )不相交，
 * 则称活动i与活动j是相容的。当 si ≥ fj 或 sj ≥ fi 时，活动i与活动j相容。
 * 活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。
 *
 *
 * @author 滑技工厂 https://blog.csdn.net/qq_41718454
 * @date 2020/6/5
 * @version 1.0
 */
public class ActivityArrangement {

    /*
     * @Title chooseActivity
     * @Description 选择活动方法
     * @author 滑技工厂
     * @Date 2020/6/5
     * @param [activities]
     * @return boolean[] 返回活动选择数组
     * @throws
     */
    public static boolean[] chooseActivity(Activity[] activities) {
        int n = activities.length;
        //用来表示原活动序列（未排序）是否被选中
        boolean[] flags = new boolean[n];

        //把序列按照结束时间进行升序排序
        Arrays.sort(activities);

        //结束时间指针
        int flag = 0;

        for (int i = 0; i < n; i++) {
            //排序之后，如果一个活动的开始时间在指针之后或相等，那么便可以举办这个活动
            if (activities[i].starttime>=flag){
                //举办活动 更新结束时间指针
                flag = activities[i].finaltime;
                flags[activities[i].index] = true;
            }
        }
        return flags;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        Activity activities[] = new Activity[n];

        for (int i = 0; i < n; i++) {
            activities[i] = new Activity();
            activities[i].index = i;
            activities[i].starttime = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            activities[i].finaltime = sc.nextInt();
        }

        boolean[] flags = chooseActivity(activities);

        for (boolean flag : flags) {
            System.out.print(flag+" ");
        }

    }

}
/**
 * @ClassName Activity
 * @Description 活动类
 * @author 滑技工厂 https://blog.csdn.net/qq_41718454
 * @date 2020/6/5
 * @version 1.0
 */
class Activity implements Comparable<Activity> {
    int index;
    int starttime;
    int finaltime;
    /*
     * @Title compareTo
     * @Description 排序方法
     * @author 滑技工厂
     * @Date 2020/6/5
     * @param [activity]
     * @return int 1表示this对象要排前面 -1表示不排前面
     * @throws
     */
    @Override
    public int compareTo(Activity activity) {
        if (activity.finaltime > this.finaltime)
            return -1;
        else if (activity.finaltime == this.finaltime)
            return 0;
        else
            return 1;
    }

好久没更新十分抱歉，感到有帮助的话请给个大大的点👍，给我一些些的动力🙏🙏