P4806 丰富的周日生活（基础）

解题思路

1. 读懂题目：周日有很多活动，每项活动有开始时间和结束时间。小童参加活动善始善终，一个活动结束前不会中途退出。他想要参加尽可能多的活动。

2. 打个比方：就像安排一天的行程，先把结束早的事情做完，剩下就有更多时间去做后面的事情。

3. 第一步：把所有活动按"结束时间"从早到晚排序。结束早的活动优先考虑。

4. 第二步：用一个变量 lastEnd 记录上一个参加的活动是什么时候结束的，一开始它等于 0（周日刚开始）。

5. 第三步：按顺序看每个活动，如果这个活动的开始时间 ≥ lastEnd，说明它和上一个活动不冲突，就参加它，然后把 lastEnd 更新为它的结束时间。

6. 为什么贪心正确：每次选择"结束时间最早而且和之前不冲突"的活动参加，就能给后面的活动留下最多的空余时间，所以参加的活动数量一定是最多的。

7. 边界情况：如果一个活动结束时间正好等于下一个活动的开始时间，那么两个都能参加，因为判断条件是"开始时间 ≥ 上一个结束时间"，等于也算可以；多个活动结束时间相同也没关系，先看哪个都一样。

参考代码

// P4806 丰富的周日生活：活动安排贪心，按结束时间早的优先参加，能参加最多活动
#include <iostream>
#include <algorithm>
using namespace std;

struct Activity {
    int start;   // 活动开始时间
    int end;     // 活动结束时间
};

Activity activity[200005];   // 每项活动

// 按结束时间从早到晚排序，结束早的活动先安排
bool cmp(const Activity& a, const Activity& b) {
    if (a.end != b.end) return a.end < b.end;
    return a.start < b.start;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> activity[i].start >> activity[i].end;
    sort(activity, activity + n, cmp);
    int lastEnd = 0;   // 上一个参加的活动结束时间
    int cnt = 0;       // 能参加的活动数量
    for (int i = 0; i < n; i++) {
        if (activity[i].start >= lastEnd) {
            cnt++;              // 这项活动开始时间不冲突，参加它
            lastEnd = activity[i].end;
        }
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

排序需要 O(n log n) 的时间，排序后再扫描一遍所有活动判断是否参加，需要 O(n)。所以总时间复杂度是 O(n log n)，空间复杂度是 O(n)。