精华内容
下载资源
问答
  • Java- 活动安排(贪心算法)
    2021-05-07 14:57:46

    题目描述

    有n份兼职,每份兼职有一个开始时间和一个结束时间,假设你的空闲时间为从1到m,假如你的休息时间可以忽略,
    请你选择若干份兼职(每次只能做其中一个兼职),使你在该段空闲时间内完成的兼职份数最大。

    输入:第一行为两个整数n,m分别表示n份兼职,空闲时间为1到m(1<=n<=1e4,1<=m<=1e5)。
    接下来n行每行有2个整数a,b。表示该兼职开始和结束时间(1<=a<=b<=m)。

    输出:输出你在1到m时间段内最多能完成几份兼职。

    算法分析

    如何选择,才是贪心的最优解

    • 将原数据,按照开始时间排序
    • 将原数据,按照结束时间排序
    • 将原数据,按照完成最短时间排序

    直观发现只有按照结束时间排序才是最佳选择,其他两种都有直观的反例,由于能力欠缺 具体证明 不再详述。致歉

    代码展示

    仅供参考

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    import java.util.Arrays;
    import java.util.Comparator;
     
     
    public class Main {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
         
        public static void main(String[] args) {
            int n = nextInt();
            int m = nextInt();
            int[][] A = new int[n][2];  // A[i][0]代表活动i的开始时间,A[i][1]代表结束时间
            
            for (int i = 0; i < n; i++) {
                A[i][0] = nextInt();
                A[i][1] = nextInt();
            }
            // 重写比较器,按照结束时间升序
            Arrays.sort(A, new Comparator<int []>() {
                 public int compare(int[] a, int[] b) {
                    return a[1] - b[1];
                }
            });
           
            int cnt = 1;  // 活动数
            int j = 0;  // 当前活动的 下标
            // 当下一个活动
            for (int i = 1; i < n; i++) {
                if (A[i][0] >= A[j][1]) {
                    cnt++;
                    j = i;
                }
            }
            System.out.println(cnt);
             
        }
         
        static int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int)in.nval;
        }
    }
    

    感谢努力
    加油!

    更多相关内容
  • java 活动安排 文件包

    2012-10-17 13:09:42
    在共用一个资源情况下,以活动时间允许的情况研究最多可以安排活动个数。
  • JAVA实现活动安排

    2020-06-26 21:41:45
    8、实验七活动安排 实验内容 设有n个活动的集合E={1, 2, … n}, 其中每个活动都要求使用同一资源且在同一时间内只有一个活动能使用这一资源。要求根据下述两种贪心准则,给出活动集合中最大的相容活动子集合。 (1)...

    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...

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

        有11项考试要安排,每项活动 i 的开始时间为 \large s_{i} (start),结束时间为 \large f_{i} (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);
    
            }
    }
    

    展开全文
  • 活动安排java

    2011-11-23 15:50:54
    活动安排java版,算法分析与设计的实验课作业,用java实现。
  • 活动安排问题(贪心、Java)问题分析代码 又是好久没更,最近一直在忙杂七杂八的,更一个算法作业吧。 问题 X轴上有N条线段,每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。(注:起点或终点重叠,...

    活动安排问题(贪心、Java)

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

    问题

    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相容。
    活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。
    图片来自https://www.jianshu.com/p/5a97bcc407fa?tdsourcetag=s_pctim_aiomsg

    分析

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

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

    在这里插入图片描述
    那我们就让剩余的时间段连续起来,还要最大,那么我们就选择结束时间最早的,这样留出来的是整块的时间还挺大。
    在这里插入图片描述

    代码

    /**
     * @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;
        }
    

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

    在这里插入图片描述

    展开全文
  • 简单活动安排的算法 event.java 对于算法书上有用
  • 算法思想:贪心算法实际问题:活动安排问题编写语言:Java问题描述设有n个活动的集合 E = {1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有...
  • 活动安排问题—贪心算法—java实现

    千次阅读 2018-04-25 23:05:43
    在所给的活动集合中选出一个最大的相容活动子集和。 设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源(如一个阶梯教室等),而在 同一时间内只有一个活动能使用这一资源。 1、每个活动i都有一个...
  •   注意活动安排问题的开始时间s[ i ]是非降序排列的,结束时间f[ j ]也是非降序排列的,所以可证明活动安排满足贪心算法,因为除去第一个活动,假设第一个活动是活动k,那么总有f1<=fk,则A-{ k } U { 1 }与 以...
  • 贪心算法在活动安排问题中的应用 问题描述 有若干个活动,第i个开始时间和结束时间是[Si,fi),只有一个活动场地可以利用,活动之间不能交叠,求最多安排多少个活动? 问题分析 活动安排问题就是要在所给的活动...
  • 贪心算法活动安排
  • 活动选择问题描述 假设我们存在这样一个活动集合S={a1,a2,a3,a4,...,an},其中每一个活动ai都...现在这些活动占用一个共同的资源,就是这些活动会在某一时间段里面进行安排,如果两个活动aiai和ajaj的占用时间[si,f...
  • 活动安排问题算法的java实现(贪心算法) 具体问题描述以及C/C++实现参见网址 http://blog.csdn.net/liufeng_king/article/details/8683136
  • 活动安排问题描述: 设有n个活动的集合E={1,2,......,n},每个活动要是用同一个资源,而在同一时间内只能让一个活动使用。每个活动i都有对应的开始时间si和结束时间fi,且si。该问题就是要求出所给的活动集E中...
  • 活动安排的贪心算法

    千次阅读 2019-11-07 10:12:43
     活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的...
  • 贪心算法之活动安排问题

    千次阅读 2018-07-24 23:26:34
    下面给出的解活动安排问题的算法GreedySelector中,各活动的起始时间和结束时间分别存储在数组s和f中,且按结束时间升序排序,即 f1≤f2≤f3≤......≤fn。如果所给出的活动集合未按此序排序,可以用O(nlogn)的时间...
  • 设有n个活动的集合E={1,2,……,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果...
  • 设有n个活动的集合E={1,2,----,n},其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它...
  • 会议安排问题JAVA实现

    2022-04-28 22:38:49
    会议安排问题JAVA实现
  • 活动安排问题 之 贪心算法

    千次阅读 2019-03-22 13:20:10
    活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动...
  • 实验三 贪心法解活动安排问题 一实验内容及要求 1要求按贪心法求解问题 2要求读文本文件输入活动安排时间区间数据 3要求显示结果 二实验仪器和软件平台 仪器 普通电脑一台 软件平台 WIN-XP + MyEclipse 6.0 三源程序...
  • 活动安排算法

    2021-02-20 11:53:51
    1.活动安排问题可以用贪心算法求解,从贪心算法的思想出发,总是作出当前最好的选择,并不需要从整体最优考虑,完成的是局部最优选择,整体最优解可以通过一系列局部最优的选择当然活动安排问题用贪心算法求解则是...
  • 会场安排问题Java实现

    2019-11-13 21:20:08
    import java.util.ArrayList; import java.util.List; public class MeetingPlaceProblem { private static Integer endTime[] = {23, 28, 35, 80, 50};//结束时间 private static Integer[] startTime = {1, ...
  • 活动安排问题(贪心算法)求解 问题描述: 设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。 每个活动i都有一个要求使用该资源的起始...
  • 使用jar包示例 博文链接:https://xinglijun1973.iteye.com/blog/1822951
  • zhaoqian.javapublic class zhaoqian { public static void main(String[] args) { int m[]={25,10,5,1}; int n=99; int[] num=new int[m.length];

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,023
精华内容 10,009
关键字:

java活动安排

java 订阅