Description
A restaurant received n orders for the rental. Each rental order reserve the restaurant for a continuous period of time, the i-th order is characterized by two time values — the start time li and the finish time ri (li ≤ ri).
Restaurant management can accept and reject orders. What is the maximal number of orders the restaurant can accept?
No two accepted orders can intersect, i.e. they can't share even a moment of time. If one order ends in the moment other starts, they can't be accepted both.
Input
The first line contains integer number n (1 ≤ n ≤ 5·105) — number of orders. The following n lines contain integer values li and rieach (1 ≤ li ≤ ri ≤ 109).
Output
Print the maximal number of orders that can be accepted.
Sample Input
Input
2
7 11
4 7
Output
1
Input
5
1 2
2 3
3 4
4 5
5 6
Output
3
Input
6
4 8
1 5
4 7
2 5
1 3
6 8
Output
2
/*
题意：给你餐厅n组客人就餐时间（起始时间，终止时间）如果时间有重叠的话，那么两组客人不能同时用餐，问餐厅最多接纳多少组客人 初步思路：按照终止时间排序，然后贪心 */
#include <bits/stdc++.h>
using namespace std;
struct node{
int Frist,End;
bool operator <(const node &other) const{
return End<other.End;
}
}fr[];
int n;
int res=;
int last=;
void init(){
res=;
last=;
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
init();
for(int i=;i<n;i++){
scanf("%d%d",&fr[i].Frist,&fr[i].End);
}
sort(fr,fr+n);
for(int i=;i<n;i++){
if(fr[i].Frist>last){
res++;
last=fr[i].End;
}
}
printf("%d\n",res);
}
return ;
}