$\LARGE\color{orange}{刷题日记(算法提高课)}$

由于南北两岸的城市一一对应，因此我们可以用 pair 来存储一对数

我们假定南岸城市的坐标为 first ，北岸城市的坐标为 second

当我们对 first 排序后（递增），如果期望每一对对组都不会相交，那么我们可以得出： second 的值也必须递增

举个例子，如果 $i\ <\ j$ （表示南岸坐标），此时有 $a[i]\ >\ a[j]$ （表示北岸坐标），那么它们就是相交的

由于我们需要求在不相交的情况下的最大对组数，因此我们考虑将 first 看作数组下标，second 当中数组元素值，在此数组的基础上做 LIS ，最后得到的结果就是答案

说明：这种对应关系的问题首先想到的应该是直接用 pair ， unordered_map 可以作为第二考量

完整代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5010;

typedef pair<int, int> PII;

int f[N];
PII a[N];
int n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }

    sort(a + 1, a + n + 1);

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(a[j].second < a[i].second) f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}