1.区间选点 区间问题

 

区间问题一般都需要对区间进行排序，对左端点排序，或对右端点排序，或双关键字排序

 然后需要证明这样的选法选出来的点数一定是符合答案的，且是选点最少的

 首先按照这个方法来选的话，每一个区间上一定选了一个点，所以这种选法是一种合法的方案

然后这道题的最优解是指所有合法方案中的选点最少的，所以

 

 

 所以ans = cnt

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Range {
    int l, r;
} range[N];
bool cmp(Range r1, Range r2) {
    return r1.r < r2.r;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }
    sort(range, range + n, cmp);
    int res = 0, ed = -2e9;
    //ed表示上一个点的下标
    for (int i = 0; i < n; i++) {
        if (range[i].l > ed) {
            res++;
            ed = range[i].r;
        }
    }
    cout << res << endl;
    return 0;
}