P4786 童童看节目（基础）

解题思路

第一步，读懂题目。 童童寒假要看电视，有 n 个节目，每个节目有开始时间 s_i 和结束时间 e_i。童童只看完整的节目，问他最多能完整看几个节目。输入有多组数据，n=0 时结束。

第二步，想到贪心。 这是经典的“活动安排”问题。为了看到尽量多的节目，我们应该按结束时间从早到晚排序，然后依次选择：只要当前节目的开始时间不早于上一个选中节目的结束时间，就选它。

第三步，为什么按结束时间排序？ 因为结束得越早的节目，占用的时间越靠前，给后面的节目留下的时间越多，越有机会多看几个。就像安排一天的学习任务，先把早结束的任务排前面，后面才接得上更多任务。

第四步，处理相邻节目。 如果一个节目 3 点结束，另一个 3 点开始，童童可以连着看，所以判断条件是“开始时间 >= 上一个的结束时间”。

第五步，处理多组数据。 题目说 n=0 时输入结束，所以要用 while 循环不断读 n，读到 0 就退出。

第六步，举一个例子。 节目有 (1,3)、(3,4)、(0,7)、(3,8)、(5,10)、(10,15)、(15,19) 等，按结束时间排序后：先选 (1,3)，接着 (3,4) 能接上，再选 (5,10)，再选 (10,15)，再选 (15,19)，一共 5 个，这就是最多能看的数量。

第七步，处理特殊情况。 如果一个节目在另一个节目结束的那一刻开始，是可以连着完整看完的，所以判断条件用“开始时间大于等于上一个的结束时间”。如果两个节目的结束时间相同，就让开始时间早的排前面，这样它占用的时间段更短，不会妨碍后面的节目。

参考代码

// 童童看节目：活动安排问题，把节目按结束时间从小到大排序，能接上就选，这样能看到的最多
#include <iostream>
#include <algorithm>
using namespace std;

struct Show {
    int start;
    int end;
};

// 比较函数：结束时间早的排在前面；结束时间相同则开始时间早的在前
bool compareEnd(const Show &a, const Show &b) {
    if (a.end != b.end) return a.end < b.end;
    return a.start < b.start;
}

Show shows[105];

int main() {
    while (true) {
        int n;
        scanf("%d", &n);
        if (n == 0) break; // n 为 0 时结束输入
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &shows[i].start, &shows[i].end);
        }
        sort(shows, shows + n, compareEnd);
        int count = 0;
        int lastEnd = 0;
        for (int i = 0; i < n; i++) {
            // 只有当前节目的开始时间不早于上一个选中节目的结束时间，才能完整观看
            if (shows[i].start >= lastEnd) {
                count++;
                lastEnd = shows[i].end;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

复杂度分析

每组数据排序需要 O(n log n)，贪心扫描一遍是 O(n)，总时间复杂度 O(n log n)。题目中 n 不超过 100，即使有多组数据也很快。空间 O(n)。