---
tags: YTP/APCS 練習題單
---
# f608: 4. 飛黃騰達
連結:https://zerojudge.tw/ShowProblem?problemid=f608

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
pair <int, int> point[N];
bool cmp(pair<int, int> point1, pair <int, int> point2){
    if (point1.first != point2.first) return point1.first < point2.first;
    else return point1.second < point2.second;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 0;i < n;i ++) cin >> point[i].first >> point[i].second;
    sort(point, point + n, cmp);
    vector <int> v;
    for(int i = 0;i < n;i ++){
        if (v.empty() || v.back() <= point[i].second) v.push_back(point[i].second);
        else v[upper_bound(v.begin(),v.end(), point[i].second) - v.begin()] = point[i].second;
    }
    cout << v.size() <<endl;
}