正文

贪心基础入门讲解三——活动安排问题二

一蓑烟雨任生平  一蓑烟雨任生平  2022-08-19  506

关键词：

有若干个活动，第i个开始时间和结束时间是[Si,fi)，活动之间不能交叠，要把活动都安排完，至少需要几个教室？

分析：能否按照之一问题的解法，每个教室安排尽可能多的活动，即按结束时间排序，再贪心选择不冲突的活动，安排一个教室之后，剩余的活动再分配一个教室，继续贪心选择……

反例： A：[1,2) B：[1,4) C：[5,6) D：[3，7)

已经按结束时间排好顺序，我们会选择
教室1： A C
教室2: B
教室3: D
需要3个教室。
但是如果换一种安排方法，我们可以安排AD在一个教室，而BC在另外一个教室，两个教室就够了。

所以之前的贪心策略解决不了这个问题。

怎么办？之前的策略是用一个教室找所有它能安排下的活动，即用教室找活动，我们能不能用活动找教室呢？

策略：按照开始时间排序优先安排活动，如果冲突，则加一个教室。
简单地理解一下，策略是这样，我们把活动按照开始时间有小到大的顺序排序。假设目前已经分配了k个教室（显然k初始等于0），对于当前这个活动，
（1）如果它能安排在k个教室里的某一个，则把它安排在其中的任何一个教室里，k不变。
（2）否则它和每个教室里的活动都冲突，则增加一个教室，安排这个活动。

这个策略是最优么？

我们想像一下k增加1的过程：因为我们是按照开始时间排序的，意味着当前考虑的这个活动开始的时候，k个教室里都有活动没结束（因为如果有一个教室的活动结束了，我们就可以安排这个活动进入那个教室而不冲突，从而不用增加k)。这就意味着在这个活动开始的时间点，算上目前考虑的这个活动，有(k + 1)个活动正在进行，同一时刻有(k + 1)个活动在进行，无论我们如何安排教室，都至少需要(k + 1)个教室。因为每个教室里不能同时进行两个活动。而我们的策略恰好需要(k + 1)个教室，所以是最优的。

这个策略也告诉我们，如果从时间轴上“宏观”考虑这个问题。考虑每个时间点同时进行的活动个数，作为这个时间点的厚度（把活动开始和结束时间想像成线段，那么每个时间点有多少条线段覆盖它，可以简单理解为“厚度”），我们至少需要最大厚度那么多个教室——因为那时恰好有最大厚度那么多个活动同时进行，而我们这个贪心策略恰好给了我们一个用最大厚度那么多个教室安排全部活动的一个方案。

如果只需要教室的个数，我们可以把所有开始时间和结束时间排序，遇到开始时间就把厚度加1，遇到结束时间就把厚度减1，显然最初始和最后结束时的厚度是0，在一系列厚度变化的过程中，峰值（最大值）就是最多同时进行的活动数，也是我们至少需要的教室数。

输入

第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000

输出

一行包含一个整数表示最少教室的个数。

输入示例

输出示例

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。

不同语言如何处理输入输出，请查看下面的语言说明。

#include<cstdio>  
#include<algorithm>  
using namespace std;  
struct node  
{  
    long long str;  
    long long end;  
}arr[10000+11];  
bool cmp(node a,node b)  
{  
    if(a.str==b.str)  
        return a.end<b.end;  
    return a.str<b.str;  
}  
long long b[10000+11];   
int main()  
{  
    int n;  
    scanf("%d",&n);  
    for(int i=0;i<n;++i)  
        scanf("%lld%lld",&arr[i].str,&arr[i].end);  
    sort(arr,arr+n,cmp);  
    b[0]=arr[0].end;//记录结束的时间  
    int i,j;  
    long long sum=1;  
    for(i=1;i<n;++i)  
    {  
        for(j=0;j<sum;++j)   
        {  
            if(arr[i].str>=b[j])//成立代表可以用这个教室，教室不增加，更新结束时间   
            {  
                b[j]=arr[i].end;  
                break;   
            }   
        }   
        if(j==sum)//代表找不到教室，那就增加教室并更新结束时间   
        {  
            b[sum]=arr[i].end;  
            ++sum;   
        }   
    }  
    printf("%lld
",sum);   
    return 0;   
}

如果对你有所帮助，别忘了加好评哦；么么哒！！下次见！88

贪心基础入门讲解四——独木舟问题

...分析：一个显然的策略是按照人的体重排序。极端化贪心策略，最重的人要上船——如果最重的人和最轻的人体重总和不超过船的承重，则他们两个占用一条船。否则（因为假设最重的人的体重也不超过船的承重了查看详情

贪心基础入门讲解五——任务执行顺序

...要“最有利”的一种执行顺序。大家可以尝试多种贪心策略。我查看详情

贪心入门——活动安排问题

贪心入门的几个例题来自51nod问题描述　　有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？输入第1行：1个数N，线段的数量(2<=N<=10000)第2-N+1行：每行2个数，线... 查看详情

贪心基础入门讲解一——完美字符串

约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。约翰不在乎字母大小写。（也就是说字母F和f）的完美度相同。给定一个字... 查看详情

新手入门linux的步骤

...路线，这样才可以达到事半功倍的效果。第一阶段：linux基础入门1.开班课程介绍-规章制度介绍-破冰活动；2.Linux硬件基础/Linux发展历史；3.Linux系统安装/xshell连接/xshell优化/SSH远程连接故障问题排查4.第一关一大波命令及特殊字... 查看详情

springboot入门基础：介绍

一.SpringBoot初级（一）SpringBoot入门SpringBoot简介构件SpringBoot项目以及启动器讲解SpringBoot入门HelloWorld（二）SpringBoot整合Web开发整合Servlet整合Filter整合Listener访问静态资源文件上传（三）SpringBoot视图层技术整合jsp技术整合freemarker... 查看详情

如何入门爬虫（基础篇）

...、爬虫入门Python爬虫入门一之综述Python爬虫入门二之爬虫基础了解Python爬虫入门三之Urllib库的基本使用Python爬虫入门四之Urllib库的高级用法Python爬虫入门五之URLError异常处理Python爬虫入门六之Cookie的使用Python爬虫入门七之正则表... 查看详情

浅谈如何学习linux

...Linux经典学习路线，希望对你们有帮助。第一阶段：linux基础入门1.开班课程介绍-规章制度介绍-破冰活动;2.Linux硬件基础/Linux发展历史;3.Linux系统安装/xshell连接/xshell优化/SSH远程连接故障问题排查4.第一关一大波命令及特殊字符知... 查看详情

想学linux应该怎么入手

...果，初学者可以按照以下路线进行学习：第一阶段：linux基础入门1.开班课程介绍-规章制度介绍-破冰活动;2.Linux硬件基础/Linux发展历史;3.Linux系统安装/xshell连接/xshell优化/SSH远程连接故障问题排查4.第一关一大波命令及特殊字符知... 查看详情

linux课程有啥内容？

Linux学习，主要学以下内容：第一阶段：linux基础入门1.开班课程介绍-规章制度介绍-破冰活动；2.Linux硬件基础/Linux发展历史；3.Linux系统安装/xshell连接/xshell优化/SSH远程连接故障问题排查4.第一关一大波命令及特殊字符知识考试题... 查看详情

python_分治算法贪心算法动态规划算法(代码片段)

...思想2、寻找假币示例二、贪心算法1、思想2、最大不相容活动安排示例三、动态规划1、思想2、最大和路径3、背包问题4、动态规划和贪心算法的区别一、分治算法思想分治算法是一种化繁为简的算法思想。分治算法往往应用于... 查看详情

zznuoj_java语言从非零基础到入门讲解(代码片段)

ZZNUOJ_Java语言从非零基础到入门讲解一、什么是Java二、Java语言非零基础三、Java语言入门练习一、什么是JavaJava是一种语言，和C语言的语法写法差不多，但是比C语言不错，需要先学会了C语言后就容易看懂Java语言(C语... 查看详情

zznuoj_java语言从非零基础到入门讲解(代码片段)

linux课程主要讲啥内容？

python基础入门和介绍，讲解python环境安装，pycharm安装教程(代码片段)

文章目录一、Python介绍二、Python特点三、Python行情如何？四、Python怎么学？5.1学理论——懂原理五、Python安装第1步：默认版本下载第2步：指定版本下载第3步：拉到最下面第4步：点击安装即可六、Pycharm安... 查看详情

贪心5--活动选择

贪心5--活动选择一、心得二、题目和分析问题描述：有一个需要使用每个资源的n个活动组成的集合S= {a1，a2，···，an },资源每次只能由一个活动使用。每个活动a都有一个开始时... 查看详情

入门必看-算法基础知识讲解小白都也能看得懂(代码片段)

💂个人主页:IT学习日记🤟版权:本文由【IT学习日记】原创、在CSDN首发、需要转载请联系博主💬如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦💅想寻找共同成长的小伙伴，请点击【技... 查看详情