//众神云集、群魔乱舞、以一抵百、砥砺前行//4151:电影节

今天药忘吃喽~ 2023-02-14 02:24 13阅读 0赞

## 题目描述 ##

描述  
大学生电影节在北大举办! 这天，在北大各地放了多部电影，给定每部电影的放映时间区间，区间重叠的电影不可能同时看（端点可以重合），问李雷最多可以看多少部电影。

输入  
多组数据。每组数据开头是n(n<=100)，表示共n场电影。  
接下来n行，每行两个整数(0到1000之间)，表示一场电影的放映区间  
n=0则数据结束  
输出  
对每组数据输出最多能看几部电影  
样例输入  
8  
3 4  
0 7  
3 8  
15 19  
15 20  
10 15  
8 18  
6 12  
0  
样例输出  
3  
来源  
Guo Wei

## 题解 ##

第一种想法：按结束时间排序，统计个数。  
第二种想法：区间包含。遇到一个区间包含另一个区间时，选择所占区间小的区间，否则就按开始时间从小到大排。

代码如下：

#include<algorithm>
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<cstring>
    using namespace std;
    typedef struct
    {
        
        int x,y;
    } NODE;
    NODE a[105];
    bool cmp(NODE q,NODE w)
    {
        
        return q.y<w.y;
    }
    int main()
    {
        
        int n;
        while(cin>>n&&n)
        {
        
            for(int i=1; i<=n; i++)
                cin>>a[i].x>>a[i].y;
                sort(a+1,a+n+1,cmp);
            int ans=1;
            int temp=a[1].y;
            for(int i=2; i<=n; i++)
            {
        
                if(a[i].x>=temp)
                {
        
                    ans++;
                    temp=a[i].y;
                }
            }
            cout<<ans<<'\n';
        }
        return 0;
    }