贪心模型总结
区间最大不相交覆盖/会议安排问题
Statement
有 \(n\) 场会议要使用会议室，第 \(i\) 场会议室的开始和结束时间点为 \(l_i\) 和 \(r_i\)，不同会议时间不能重叠。求最多能安排的会议场数。
Solution
考虑将会议按 \(r_i\) 升序排序。
每次枚举到一个会议 \(i\)，检查当前最晚的会议结束时间 \(cur\) 是否小于 \(l_i\)。
若 \(cur \leq l_i\)，选择当前会议，令 \(cur \gets r_i\)。
Proof
考虑第 \(1\) 个会议，显然结束时间越早对后面的会议妨碍越少。
而对于第 \(k\) 个会议也是同理的。如果 \(cur \leq l_i\)，那么说明这是当前能选的会议中开始时间最早的，选它不会使决策更差。
由数学归纳法可知，该贪心是正确的。
sort(a+1,a+1+n);
int cur=-1;
for (int i=1; i<=n; ++i)
if (a[i].l>=cur)
cur=a[i].r, ans++;
区间最小覆盖问题
Statement
给定区间 \([L,R]\) 和 \(n\) 个小区间 \([l_i,r_i]\)，求出最少的小区间数量，使得它们的并为 \([L,R]\)。
Solution
将小区间以 \(l_i\) 为第一关键字升序排序，\(r_i-l_i+1\) 为第二关键字升序排序。设当前并的右端点为 \(cur\)，若 \(r_i\leq cur\) 则忽略，否则直接令 \(r_i=cur\)。
Proof
显然。
区间选点问题
Statement
给定数轴上的 \(n\) 个区间 \([l_i,r_i]\)，在数轴上放置若干个点，使得每个区间里至少有一个点。求最少点数。
Solution
考虑将区间按 \(r_i\) 升序排列。
对于一个区间，若其里面没有点，则取 \(r_i\) 这个点。
Proof
设正确答案为 \(ans\)，我们利用贪心选出的答案为 \(cnt\)。
由定义可知 \(ans\leq cnt\)。只需证明 \(ans\geq cnt\)。
贪心过程中我们显然找到了 \(cnt\) 个无交的区间，而在这些区间中，一个点只能覆盖一个区间。
故 \(ans\geq cnt\)。\(\square\)