看电影

[编程题]看电影

热度指数：132 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

暑假就要到了，乐乐打算好好看电影。现在已经知道每个电影的开始时间和结束时间，请你帮他计算一下，最多可以看多少部电影。一部电影用[s,t]表示，只有这个区间的时间都在看这边电影，才算看了这部电影。

输入描述:

第一行一个整数n，表示电影的个数。
接下来n行，每行两个整数，表示一部电影的起始时间和结束时间。
对于100%的数据，n和时间起始点都不超过100000。

输出描述:

输出最多可以完整看到的电影数量。

示例1

输入

输出

算法知识视频讲解

秃头凡

/*
    解题思路：将所有电影按结束时间从大到小排序，第一步选结束时间最早的那部电影。然后，
                每步都选和上一步选中的电影不冲突且结束时间最早的电影。
*/

#include <iostream>
#include <cstdio>
#include <queue>
#define MAXN 100000
using namespace std;
struct Film{
    int begin,end;        //电影开始和结束时间
    bool operator < (const Film & f) const {
        return end > f.end;
    }
};

Film films[MAXN];

int main(){
    int n,end,num;        //num用来计算能看的电影场数
    priority_queue <Film> p;
    while(scanf("%d",&n)){
        if(n == 0){
            break;
        }
        //把电影装入优先队列，按照结束时间从小到大
        for(int i = 0; i < n; i++){
            scanf("%d%d",&films[i].begin,&films[i].end);
            p.push(films[i]);
        }
        //队列不为空时，至少可以看一部电影，end值为队首电影的结束时间
        if(!p.empty()){
            num = 1;
            end = p.top().end;
            p.pop();
        }
        while(!p.empty()){
            //如果上一部电影的结束时间早于这一部电影的开始时间，则可以看这部电影
            if(!p.empty() && end <= p.top().begin){
                num++;
                end = p.top().end;
            }
            p.pop();
        }
        cout << num << endl;
    }
    return 0;
}

发表于 2020-03-04 12:06:17 回复(0)