【题目描述】

有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;    }

(adsbygoogle = window.adsbygoogle || []).push({});