P138(基础班笔记)

难点在于：

你得知道是否用贪心算法可以得到最优解，即证明ans == cnt ?

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int n;

struct Range {
    int l, r;
    bool operator < (const Range &w) const {
        return r < w.r;
    }
} range[N];

int main (){
    scanf("%d", &n);
    int l, r;
    for (int i = 0; i < n; i ++) { //读入每一个区间
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n); //结构体排序，在结构体中重载小于号 < 

    int res = 0, ed = -2e9; // ed 代表上一个点在数轴上的位置，初始是负无穷，因为第一点的上一个点没选
    for (int i = 0; i < n; i ++) {
        if (ed < range[i].l) {
            res ++;
            ed = range[i].r; //更新为当前区间的右端点
        }
    }

    printf("%d\n", res);
    return 0;
}