今年暑假不AC 王道机试指南区间贪心

题目

“今年暑假不AC？”

“是的。”

“那你干什么呢？”

“看世界杯呀，笨蛋！”

“@#$%^&*%…”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。

作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input

Sample Output

分析

这是一道经典的贪心问题 区间贪心

首先说说贪心法。贪心法就是遵循某种规则，不断贪心地选取当前最优策略地算法设计方法。

再回到这个问题，我们可以设计出各种各样的贪心算法，例如以下：

（1）在可选的节目中，每次选取开始时间最早的节目

（2）在可选的节目中，每次选取结束时间最早的节目

（3）在可选的节目中，每次选取播放时间最短的节目

在以上举例算法中，只有算法二是正确的，其它两个算法都可以找到反例，即非最优解

先看哪个节目不应该以节目开始时间的早晚为判断依据，而应该以

结束时间作为判断看与不看的依据，因为假如0点开始一个节目，持续时间无限长，就没有办法再看其他节目。

将每个节目作为结构体存储，按照节目的结束时间从早到晚进行排序。依次选择节目，如果下一个节目的开始时间在上一个节目的结束时间之后或与之相等，结果就加一。

代码

// 2023-4-17 今年暑假不AC 这是一个区间贪心的问题
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=110;
//因为每个节目的数据 包括开始时间和结束时间，采用结构体类型
struct Program
{
    int starttime;
    int endtime;
};
bool Compare(Program x, Program y)
{
    return x.endtime<y.endtime;//按照节目的结束时间按从早到晚排序
}
int main()
{
    Program pro[MAXN];//定义结构体数组
    int n;
    int ans=0;//最后输出的可以看的最大节目数
    while(cin>>n&&n!=0)
    {
        //if(n==0)
          //  break;//当输入n=0时，结束输入
        for(int i=0;i<n;i++)
            cin>>pro[i].starttime>>pro[i].endtime;//为节目赋值
        //经过分析，按照节目的结束时间按从早到晚排序;
        sort(pro,pro+n,Compare);
        int current=0;//记录当前时间，定义为0
        for(int i=0;i<n;i++)
        {
            if(current<=pro[i].starttime)
            {
                ans++;
                current=pro[i].endtime;

            }
        }
        //printf("%d\n",ans);
        cout<<ans<<endl;;
    }

}