算法1

将南北两岸的城市分别按坐标排序，两座城市之间的桥可以用(x, y)来表示，x, y分别为桥的两端的城市的坐标，
那么两座桥(x1, y1), (x2, y2)相交的情况就是x1 < x2 && y1 > y2。

那么若最终选择n座桥(x1, y1), (x2, y2), …, (xn, yn)没有交叉，即x1 < x2 < x3 < … < xn && y1 < y2 < … < yn。

这样就转换成了最长上升子序列（LIS）的问题了。

(动态规划) $O(n^2)$

动态规划解决LIS

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;
int f[N];
PII q[N];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        int x, y;
        scanf("%d%d", &x, &y);
        q[i] = {x, y};
    }

    sort(q, q + n);

    int res = 0;
    for (int i = 0; i < n; i ++ ) {
        f[i] = 1;
        for (int j = 0; j < i; j ++ ) {
            if (q[i].second > q[j].second) {
                f[i] = max(f[i], f[j] + 1);   
            }
        }
        res = max(res, f[i]);
    }

    cout << res << endl;

    return 0;
}

算法2

(贪心+二分) $O(nlogn)$

贪心+二分解决LIS

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;
PII a[N];
int q[N];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[i] = {x, y};
    }

    sort(a, a + n);

    int len = 0;
    q[0] = -1;
    for (int i = 0; i < n; i ++ ) {
        int x = a[i].second;
        int l = 0, r = len;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (q[mid] < x) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = x;
    }

    cout << len << endl;

    return 0;
}