时间复杂度$O(N\log{N})$

C++ 代码

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

#define x first
#define y second

const int N = 5e3 + 10;
pair<int, int> arr[N];
int f[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i].x >> arr[i].y;
    }

    sort(arr, arr + n);

    int len = 0;
    f[0] = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        if (arr[i].y >= f[len]) f[++len] = arr[i].y;
        else
        {
            int l = 1, r = len;
            while (l < r)
            {
                int mid = l + r >> 1;
                if (f[mid] >= arr[i].y) r = mid;
                else l = mid + 1;
            }
            f[l] = arr[i].y;
        }
    }
    cout << len << endl;
    return 0;
}