admin管理员组

文章数量:1664354

1203. Scientific Conference

Time limit: 1.0 second
Memory limit: 64 MB
Functioning of a scientific conference is usually divided into several simultaneous sections. For example, there may be a section on parallel computing, a section on visualization, a section on data compression, and so on. Obviously, simultaneous work of several sections is necessary in order to reduce the time for scientific program of the conference and to have more time for the banquet, tea-drinking, and informal discussions. However, it is possible that interesting reports are given simultaneously at different sections. A participant has written out the time-table of all the reports which are interesting for him. He asks you to determine the maximal number of reports he will be able to attend.

Input

The first line contains the number 1 ≤  N ≤ 100000 of interesting reports. Each of the next  N lines contains two integers  Ts and  Te separated with a space (1 ≤  Ts <  Te ≤ 30000). These numbers are the times a corresponding report starts and ends. Time is measured in minutes from the beginning of the conference.

Output

You should output the maximal number of reports which the participant can attend. The participant can attend no two reports simultaneously and any two reports he attends must be separated by at least one minute. For example, if a report ends at 15, the next report which can be attended must begin at 16 or later.

Sample

input output
5
3 4
1 5
6 7
4 5
1 3

3
Problem Author: Magaz Asanov
Problem Source: USU Internal Contest, March 2002 题意：科学讨论会议常常可分为几个不同的部分。比如，有的是讨论计算的，有的是讨论数据压缩的等等。为了节省时间，几个不同的部分往往同时举行，以便有更多时间举行宴会，喝茶，非正式讨论。并且，不同的部分都可能有精彩的报告会。给出所有报告会的时间安排表，要求你求出最多能够参加多少场报告会。
最大不相交区间数
按照每场会议结束时间贪心即可，道理和dp的想法很相似。 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
int n;
struct data
{
    int s,e;
} node[100002];
bool cmp(data a,data b)
{
    if(a.e!=b.e) return a.e<b.e;
    else return a.s>b.s;
}
int main()
{
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d%d",&node[i].s,&node[i].e);
    }
    sort(node,node+n,cmp);
    int s=0;
    int cnt=0;
    for(int i=0; i<n; i++)
    {
        if(node[i].s>=s)
        {
            cnt++;
            s=node[i].e+1;
        }
    }
    printf("%d\n",cnt);
}


本文标签： URALConferenceScientific

版权声明：本文标题：Ural 1203. Scientific Conference 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1730020956a1219457.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。