#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define ff first
#define ss second
#define maxn 10000009
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
typedef float fl;
typedef vector <int> vint;
typedef vector <vint> vvint;
typedef pair<int,int> pii;
typedef vector<pii> pvint;
typedef vector<bool> bvint;
const int inf=1e9+7;
int n;
int e[30002], dp[30002];
int main(){
    scanf("%d",&n);int ts,te;
    for(int i=1;i<=n;i++) scanf("%d %d",&ts, &te), e[te]=max(e[te], ts);
    for(int i=1;i<=30000;i++)if(e[i]==0) dp[i]=dp[i-1];else dp[i]=max(dp[i],dp[e[i]-1]+1);
    cout << dp[30000];
    return 0;
}

Edited by author 05.04.2017 17:56