G - Scientific Conference
Crawling in process...
Crawling failed
Time Limit:1000MS
Memory Limit:16384KB 64bit IO Format:%I64d & %I64u
Description
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.
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.
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.
if a report ends at 15, the next report which can be attended must begin at 16 or later.
Sample Input
| input | output |
|---|---|
5 3 4 1 5 6 7 4 5 1 3 |
3 |
题目解析：题目的意思就是：给出这个人参加会议的时间，要求求出这个人最多能参加几场会议。（期中参加每场会议到第二场开始的时候，至少要相差1分钟）
做题分析：因为是两个变量：开始和结束的时间，要进行对他们排序的话，肯定要用结构体。那么现在就考虑先对那个进行排序呢？ 为了解题方便，可以对结束时间先进性排序，要是两者相等的话，在根据开始的时间从小到大排序。排序用到的是sort函数，然后做题的时候注意细节和技巧就可以了！
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int t ,k;
struct node{
int a;
int b;
}s[100010];
int cmp(node x,node y){
if(x.b==y.b)
return x.a<y.a;
return x.b<y.b;
}
int main(){
int i,j;
while(cin>>t){
for(i=0;i<t;i++ )
cin>>s[i].a>>s[i].b;
sort(s,s+t,cmp);
k=1;j=0;
for(i=1;i<t;i++){
if(s[i].a-1>=s[j].b){
j=i;
k++;
}
}
cout<<k<<endl;
}
return 0;
}