第二课《贪心王国大冒险》第二章——时间管理大师 一、故事开场勇士的新任务1、同学们已经学会了 海盗船选小 接水选快大家信心满满地去找汉克老师。2、汉克老师说“很好但真正的贪心高手要学会——安排时间”3、于是大家来到了“活动大会”的现场 二、本课目标今天我们要学会一类非常重要的贪心问题区间问题一个超级经典模型活动选择一个核心技巧排序 选择规则 三、第一关活动选择1、 故事背景1学校有很多活动要在礼堂举办 每个活动有开始时间和结束时间 同一时间只能办一个活动2 问题最多能安排多少个活动2、 第一步大家想一想1汉克老师问我们应该怎样安排❓选开始早的选时间短的选结束早的2❌ 错误尝试一定要演出来 想法1选最早开始 可能会占很久 → 后面安排不了 想法2选最短时间 也不一定最优有可能挤在一起3、 正确贪心策略优先选择“结束时间最早”的活动4、 为什么 结束越早 → 留给后面的时间越多这句话大家一定要记住5、 解题步骤✅ 第一步排序按结束时间✅ 第二步选第一个✅ 第三步往后找 找开始时间 ≥ 上一个结束时间6、 课堂演示1活动时间(1,4) (3,5) (0,6) (5,7) (8,9)2 第一步按结束时间排序(1,4) (3,5) (0,6) (5,7) (8,9)这里刚好已排序3 第二步开始选选 (1,4)下一个必须 ≥4 → 选 (5,7)再选 (8,9)4 结果3个活动7、 参考代码#include iostream #include algorithm using namespace std; struct Node { int s, e; }; bool cmp(Node a, Node b) { return a.e b.e; // 按结束时间排序 } int main() { int n; cin n; Node a[105]; for(int i 0; i n; i) { cin a[i].s a[i].e; } sort(a, a n, cmp); int cnt 0; int last 0; for(int i 0; i n; i) { if(a[i].s last) { cnt; last a[i].e; } } cout cnt; } 四、第二关整数区间进阶题1、 故事背景1同学们遇到一个新挑战有很多区间 [2,4] [3,6] [0,2]2现在要选一些“点” 让每个区间里至少有一个点 并且点的数量最少3问最少需要选几个点2、 思考引导汉克老师问❓ 点应该怎样选才会最少3、 贪心策略先按照“右端点”排序然后看前面的区间右端点能覆盖后面的左端点吗 能覆盖就Ok,不能覆盖既要更新新的区间新的点。4、 解题步骤✅ 第一步按右端点排序✅ 第二步选第一个区间的右端点✅ 第三步如果后面的区间已经被覆盖 → 跳过否则 → 再选一个点5、 课堂演示1区间[0,2] [2,4] [3,6]2排序后[0,2] [2,4] [3,6]3选择过程右侧为 2[2,4] 被覆盖 ✅[3,6] 没覆盖 →增加一个点cnt → 右侧更新为 64 结果2个点6、 参考程序#includeiostream #includealgorithm using namespace std; int n; struct node { int l,r; }a[1001]; bool cmp(node a,node b) { return a.rb.r; }; int main() { cinn; for(int i0;in;i) { cina[i].la[i].r; } sort(a,an,cmp); int temp0,ans1; for(int i1;in;i) { if(a[temp].ra[i].l) continue ; else { tempi; ans; } } coutansendl; return 0; } 五、贪心总结1、 贪心三大套路1️⃣ 排序几乎必有按结束时间按右端点2️⃣ 选“最有利未来”的 留空间给后面3️⃣ 一路选下去不回头 六、本课易踩的坑❌ 坑1选开始时间最早 错✔ 应该选结束时间最早❌ 坑2不会排序结构体 很多学生卡在这里✔ 排序方法sort(a, an, cmp);❌ 坑3条件写错if(a[i].s last) 写成 就错❌ 坑4区间问题选左端点 错✔ 应该选右端点❌ 坑5以为所有区间题都一样 其实策略不同 七、本课总结同学们学会了新的能力时间管理术我们发现 贪心不是乱选 而是“为未来考虑的选择”汉克老师说“下一关大家将面对——更复杂的贪心与陷阱” 第三课贪心的极限与反例