P4808 区间选点（基础）

解题思路

1. 读懂题目：数轴上有 N 个闭区间 [l, r]，我们要在数轴上选尽量少的点，让每个区间里都至少有一个选中的点。注意：落在区间端点上的点也算在区间内。

2. 打个比方：就像在路上设检查站，每个区间就像一段必须被检查的路，我们要用最少的检查站覆盖所有路段。

3. 第一步：把所有区间按"右端点"从小到大排序，右端点小的排前面。

4. 第二步：用一个变量 last 记录上一个选的点的位置，一开始把它设为一个非常小的数（比所有区间左端点都小）。

5. 第三步：按顺序看每个区间，如果 last < 这个区间的左端点，说明上一个点不在这个区间里，那就在这个区间的右端点新选一个点，计数加 1，并把 last 更新为这个右端点。

6. 第四步：如果 last ≥ 区间的左端点，说明这个区间已经被覆盖了，跳过它。

7. 为什么贪心正确：右端点越早的区间越"紧迫"，点必须选在它里面。把点选在它的右端点是最划算的，因为这个位置最靠右，能顺便覆盖后面更多区间。

8. 边界情况：因为端点也算在区间内，判断是否被覆盖要用"last < left"（严格小于），而不是小于等于；区间坐标可能是负数，所以 last 的初始值要足够小。

参考代码

// P4808 区间选点：按右端点从小到大排序，贪心把点选在区间右端点上，让每个区间都有点
#include <iostream>
#include <algorithm>
using namespace std;

struct Interval {
    long long left;   // 区间左端点
    long long right;  // 区间右端点
};

Interval interval[100005];   // 每个区间

// 按右端点从小到大排序
bool cmp(const Interval& a, const Interval& b) {
    if (a.right != b.right) return a.right < b.right;
    return a.left < b.left;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> interval[i].left >> interval[i].right;
    sort(interval, interval + N, cmp);
    long long last = -4000000000000000000LL;   // 上一个选的点，先设为一个很小的数
    int cnt = 0;                               // 选的点的个数
    for (int i = 0; i < N; i++) {
        if (last < interval[i].left) {
            // 上一个点不在这个区间里，就在它的右端点新选一个点
            cnt++;
            last = interval[i].right;
        }
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

排序需要 O(N log N) 的时间，排序后再扫描一遍所有区间，需要 O(N)。所以总时间复杂度是 O(N log N)，空间复杂度是 O(N)。