每次选现在看起来最好的
这一课只练一件事：先定一条 的 ，再每一步按它选。选尽可能多的不重叠活动时，常用“结束最早的先选”。建议掌握：先 ，再 。必会还包括会找 ：按时长最长选会失败。最小示例：美术 [1, 4]、书法 [1, 2]、围棋 [2, 5]。n 到 1e5 时，排序大约 n log n 再扫一遍，比枚举 2^n 更能通过。哈夫曼树、最短路是拓展。这里不会在浏览器里运行 C++。
任务 1：先选出贪心是什么、该用哪条标准
不是凭感觉碰运气。它要先有一条 ，再每一步按它选。点不认识的词可看基础解释。
必会：能说出一条明确规则，并能用小例子验证。这里不会在浏览器里运行 C++，只练习选择和走过程。
贪心选择首先要做什么？贪心 · 必会
选尽可能多的不重叠活动，该用哪条标准？选择标准 · 必会
任务 2：按顺序给三个活动做贪心选择
最小示例：美术 [1, 4]、书法 [1, 2]、围棋 [2, 5]，目标是选尽可能多的不重叠活动。按顺序点三步：先从空选择 lastEnd = 0 开始，再选结束最早的书法 [1, 2]，最后跳过冲突的美术，选上围棋 [2, 5]。这里不会在浏览器里运行 C++。
必会：能解释每一步为什么选或不选。边界：还没选时 lastEnd = 0；不要跳过先选书法这一步。n 到 1e5 时，先排序再扫一遍，大约 n log n，比枚举 2^n 更能通过。
- struct Act { int s, e; };
- Act a[4] = {{0,0},{1,4},{1,2},{2,5}};
- sort(a + 1, a + 4, by_end); // 结束早的在前
- int lastEnd = 0, cnt = 0;
三步走完了，现在亲手把排好活动顺序的那一行敲出来： 是结束最早，所以要先按结束时间 。下面是只读脚手架，只留一空给你敲键盘。
- struct Act { int s, e; };
- bool by_end(Act x, Act y) { return x.e < y.e; } // 结束早的排在前面
- Act a[4] = {{0,0},{1,4},{1,2},{2,5}}; // 下标从 1 开始
- ; // 排好活动顺序
- int lastEnd = 0, cnt = 0;
sort(a + 1, a + 4, by_end); // 排完是 [1,2]、[2,5]、[1,4]，再从前往后选
任务 3：核对空选择，并用反例推翻错误标准
建议掌握：空选择是还没拿任何活动，cnt = 0，lastEnd = 0。现在已经选了书法 [1, 2] 和围棋 [2, 5]。如果改用“时长最长先选”，会先拿走美术 [1, 4]，这就是一个 。
必会 / 建议掌握 / 拓展：必会是说出贪心规则并用小例子验证。建议掌握是先 sort 再从左到右决策，以及会找反例。哈夫曼树、最短路是拓展，现在不用当硬门槛。
- // 空选择：cnt = 0，lastEnd = 0
- // 正确：书法 [1, 2]，再围棋 [2, 5]，共 2 个
- // 错误：先拿最长的美术 [1, 4]，只能选 1 个
- // 哈夫曼树、最短路是拓展，不是现在的必会
先选出空选择长什么样：
再选出为什么“时长最长先选”是错的：
任务 4：随机小测，看看你是否真的懂了
每次从本课题库抽出三道不同的选择题。题目与解析已通过校验，答完后看解析，不要只看分数；拿不准就回到对应任务再看一遍。