当前位置:首页 > 算法 > 正文内容

【贪心】区间调度

亿万年的星光4年前 (2021-01-30)算法4168

【题目描述】

有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(即使是开始与结束的瞬间重叠也是不允许的)。

你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?1<=n<=100000,1<=si<=ti<=10^9。

【输入】

n

n项工作的开始与结束时间

【输出】

最多参与的工作项数

【输入样例】

5
1 3
2 5
4 7
6 9
8 10

【输出样例】

3



【分析】

这个问题等价在问,数轴上有n个区间,选出最多的区间,使得这些区间不互相重叠,

我们可以用下面这个图示过程来表示:


此问题可通过贪心算法求解,我们容易想到以下4种算法

(1)在可选的工作中,每次都选取开始时间最早的工作

(2)在可选的工作中,每次都选取结束时间最早的工作

(3)在可选的工作中,每次都选取用时最短的工作

(4)在可选的工作中,每次都选取与最少可选工作有重叠的工作

显然(2)是正确的,其它3种算法都易举出反例;或者说在有些情况下,它们并不一定能得到最优解。

另一种解释:

1)与其它选择方案相比,该算法的选择方案在选取了相同数量的更早时间的工作时,其最终结束时间不会比其它方案更晚。

2)所以,不存在选取更多工作的选择方案。

证明:

显然,该算法最后选出的区间不互相重叠,下面证明所选出区间的数量是最多的。设fi为该算法所接受的第i个区间的右端点坐标,gi为某最优解中的第i个区间的右端点坐标。

命题1.1 

 当i>=1时,该算法所接受的第i个区间的右端点坐标fi<=某最优解中的第i个区间的右端点坐标gi。该命题可以运用数学归纳法来证明。对于i=1,命题显然为真,因为算法第一个选择的区间拥有最小右端点坐标。令i>1,假定论断对i-1为真,即fi-1<=gi-1。则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合;而当算法选择第i个区间时,选的是在可选区间中右端点坐标最小的一个,所以有fi<=gi。证毕。设该算法选出了k个区间,而最优解选出了m个区间。

命题1.2  

最优解选出的区间数量m=该算法选出的区间数量k。假设m>k,根据命题1.1,有fk<=gk。由于m>k,必然存在某区间,在gk之后开始,故也在fk之后开始。而该算法一定不会在选了第k个区间后停止,还会选择更多的区间,产生矛盾。所以m<=k,又因为m是最优解选出区间个数,所以m=k。综上所述,算法选出的区间是最优解。

【算法与结论】:

将所有区间按右端点坐标从小到大排序,顺序处理每个区间。如果它与当前已选的所有区间都没有重叠,则选择该区间,否则不选。



【参考答案1】

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  
const int maxn=100005;  
int N;  
int ans=0;  
struct Work   //定义工作   
{  
    int s;    //开始时间   
    int t;    //结束时间   
}w[maxn];  

bool cmp( Work w1,Work w2)  
//按工作结束时间递增排序   
{  
   return (w1.t<w2.t);  
}  
int main()  
{  
    int i,j;  
    int end;  //end记录最后所选活动的结束时间  
    scanf("%d",&N);  
    for(i=0;i<N;i++)  
        scanf("%d %d",&w[i].s,&w[i].t);  

    sort(w,w+N,cmp);  
    j=ans=0;  
    end=0;  
    for(j=0;j<N;j++)  
    {  
        if(w[j].s>end)  //若发现某项工作的开始时间比end晚   
        {  
            ans++;      //则选择当前工作   
            end=w[j].t; //将这项工作的结束时间作为end?  
        }  
    }  
    printf("%d\n",ans);  
    return 0;  
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【算法】动态规划—区间DP问题

一、定义区间DP是动态规划的一种特殊形式,主要用于解决涉及区间操作的问题,比如合并区间、分割区间、区间匹配等。其核心思想是通过枚举区间的划分点,将大区间的问题分解为小区间的子问题,逐步求解并保存中间结...

【算法】高精度(2)

五、高精度处理进位与借位    其实也很简单,我们再来模拟一下,1439+887的时候,首先我们最低位相加,得到16,那么答案最低位就是6,再进个1,然后两数的十位相加,...

【算法】归并排序

【算法】归并排序

一、基本思想归并排序的核心思想是将两个已经有序的子序列合并成一个有序序列。整个过程分为两个主要步骤: 1.分解:将待排序的序列不断二分,直到每个子序列只包含一个元素(此时自然有序) ...

【贪心】----找零钱问题

一、找零钱问题例题1:有 1 元,5元,10元,20元,100元,200元的钞票无穷多张。现在使用这些钞票支付X元,最少需要多少张钞票。X = 628最佳支付方法:3张200块的,1张20块的,1张5...

【贪心】----最优装载、背包、乘船问题

【贪心】----最优装载、背包、乘船问题

1.最优装载题目描述:有n个物体,第i个物体的重量为wi(wi为正整数)。选择尽量多的物体,使得总重量不超过C。【分析】由于只关心选择的物品的最大数量(而不是最大重量,最大重量需要考虑DP),所以装重...

【贪心】----基本概念

一、基本概念所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解。贪心算法没有固定的算法框架,算法设计的关键是贪...