美文网首页算法讲解
会场安排问题

会场安排问题

作者: 我没有三颗心脏 | 来源:发表于2017-11-25 09:19 被阅读0次

问题描述:

假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数)。

来换一个描述

为了能够更加生动说明问题的整个过程,所以换一个类似的描述来契合《算法图解》一书中的描述。

你没法让这些课都在这间教室上,因为有些课的上课时间有冲突。

你希望这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢?

这个问题似乎很难,但算法却简单得让人吃惊。具体做法如下:

  • ①选出结束最早的课,它就是要在这间教室上的第一堂课。
  • ②接下来,必须选择第一堂课结束后才开始的课。同样,你选择结束最早的课,这将是要在这间教室上的第二堂课。

重复这样做就能找出答案!下面来试一试。美术课的结束时间最早,为10:00 a.m,因此它就是第一堂课。

接下来的课必须在10:00 a.m后开始,且结束得最早。

英语课不行,因为它的时间与美术课冲突,但数学课满足条件。最后,计算机课与数学课的时间是冲突的,但音乐课可以。

因此将在这间教室上如下三堂课。

贪婪算法很简单:每步都采取最优的做法。在这个示例中,你每次都选择结束最早的课。用专业术语说,就是你每步都选择局部最优解,最终得到的就是全局最优解。听上去有些神奇,但对于这个调度问题上,上述的简单算法找到的就是最优解。

数据输入

第一行有1个正整数k,表示有k个待安排的活动。接下来的k行中,每行有两个正整数,分别表示k个待安排的活动开始时间和活动结束时间。时间以0点开始的分钟计。

由于问题定义上有些纰漏,但通常,我们认为如果上一个活动在t时间结束,下一个活动最早应该在t+1时间开始(上述问题有一定出入)

代码实现

考虑到用户输入并不会按照开始的时间或者结束的时间严格输入,所以我们自己或许要加一个排序算法,这对我们自己遍历也会提供方便:

private static int meeting_problem(int[] startTime,int[] endTime){
    //一组活动数据的最优解
    int maxresult = 1;
    //冒泡排序,对startTime和endTime数据进行排序
    for (int i = 0; i < endTime.length-1; i++) {
        boolean canBreak = true;
        for (int j = 1; j < endTime.length - i; j++) {
            if (endTime[j-1] > endTime[j]) {
                int temp = endTime[j - 1];
                endTime[j-1] = endTime[j];
                endTime[j] = temp;

                int temp2 = startTime[j - 1];
                startTime[j-1] = startTime[j];
                startTime[j] = temp2;
                canBreak = false;
            }
        }
        if (canBreak) {
            break;
        }
    }
    // 记录上一次活动的结束时间
    int key = endTime[0];
    for (int i = 1; i < endTime.length; i++) {
        // 如果活动的开始时间能够大于上一次活动的结束时间
        if (startTime[i] - key >= 1){
            //计数+1
            maxresult ++;
            //保存结束时间
            key = endTime[i];
        }
    }
    return maxresult;
}

结合输入的代码:

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int num = scanner.nextInt();
    int[] results = new int[num];
    for (int i = 0; i < num; i++) {
        int a = scanner.nextInt();
        int[] startTimes = new int[a];
        int[] endTimes = new int[a];
        for (int j = 0; j < a; j++) {
            startTimes[j] = scanner.nextInt();
            endTimes[j] = scanner.nextInt();
        }
        results[i] = (meeting_problem(startTimes, endTimes));
    }
    for (Integer result:results) {
        System.out.println(result);
    }
}

这里直接引用了 黑白咖 的文章:http://www.jianshu.com/p/0ce92abe862d 中的代码。

另外一种思路

我们也可以通过找最大重叠数来完成,这里不符合贪心策略,所以就不作深入研究。

欢迎转载,转载请注明出处!
简书ID:@我没有三颗心脏
github:wmyskxz
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料

相关文章

  • 会场安排问题

    问题描述: 假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排(这个问题...

  • acm 会场安排问题

    acm 会场安排问题链接地址题目描述:描述学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需...

  • 贪心算法会场安排问题

    会场安排问题 假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个算法进行安排。 *测试:5(活...

  • 贪心算法——会场安排问题

    最近希望在日常加强一下算法的水平,所以找了一个ACM网站来强行刷水题,不过脑子笨,刷个题老半天的,果然技术有限啊,...

  • 中学英语会场情况总结

    根据8月7日中学英语会场的情况,反馈如下: 活动安排很紧凑,但中间出现了几个问题。 1.英语会场朗诵汪国真的汉语诗...

  • ACM10

    会场安排问题 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 学校的小礼堂每天都会有许多...

  • 10.12会议复盘

    1.培训考试没有提前预约,既不尊重老师,会场安排也会比较混乱。 2.会场安排人事部应提前介入安排,业务部门提出需求...

  • 办会须知-会场座次安排

    中国自古以来讲究座次排序,今天参与了一次全市会议的小会场布置,感觉其中的门道特别多,应当予以记录。 第一,会议筹办...

  • 2天学习我所感受到的

    一、用心 体现在3个方面 1.会场布置 2.专业技术和服务 3.流程安排 从会场签到—主会场—舞台灯光—拍照区...

  • 2022-07-15 百密一疏

    明天要开会了,还是忘记了一件很重要的事情。忘记给分会场参加的总经理安排座位。 沈阳主会场的,我都安排好了。唯独忘记...

网友评论

    本文标题:会场安排问题

    本文链接:https://www.haomeiwen.com/subject/colqbxtx.html