题解 | 活动安排->DP+离散化

先将所有的起始位置进行排序，从后往前依次查看，查看到下标为 i 的位置，如果以这个位置为起点的活动要被选择的话，那么就将这个位置结束的位置+1作为结果，如果不被选择的话，就是这个位置的下一个时刻的位置作为结果。

就是：dp[i] = max(dp[i + 1], dp[k] + 1）

其中k是以i为起始，以k为结束的一个活动。如果同时有多个以i为开始的活动，则遍历每一个这样的活动，求最大值。

因为a和b的范围都是10的9次方，如果直接遍历肯定超时。

可以使用离散化的方法，虽然a b的范围很大，但是n的范围很小，也就是说数据是稀疏的，可以使用一个map将所有出现过的数据做映射，最多只有10的5次方级别的数据，所有范围就缩小了。这样直接遍历就可以了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(2));
    set<int> s;
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        s.insert(a[i][0]);
        s.insert(a[i][1]);
    }
    vector<int> x;
    for (int t : s) 
        x.push_back(t);
    sort(x.begin(), x.end());
    map<int, int> m;
    for (int i = 0; i < x.size(); i++) {
        m[x[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        a[i][0] = m[a[i][0]];
        a[i][1] = m[a[i][1]];
    }
    sort(a.begin(), a.end(), [](const vector<int>& o1, const vector<int>& o2)->bool{
        if(o1[0] != o2[0]) {
            return o1[0] < o2[0];
        } else {
            return o1[1] < o2[1];
        }
    });
    vector<int> dp(x.size() + 1);
    int lastN = n;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = lastN - 1; j >= a[i][0]; j--) {
            dp[j] = dp[j + 1];
        }
        dp[a[i][0]] = max(dp[a[i][0]], dp[a[i][1]] + 1);
        lastN = a[i][0];
    }
    cout << dp[0] << '\n';
}   
// 64 位输出请用 printf("%lld")