对于 AcWing 905. 区间选点 的数学归纳法证明

$ans$:最优解
$cnt$:按照一定规则选出的点

设$cnt(k)=ans(k)$
对于第$k+1$个区间:
如果$(k+1).l>ed$,显然移动$ed$使得$(k+1).l<ed$会使前面至少一区间无点，再想到如果继续往前移动使得该无点区间有点显然不可行，故应当增加一个点，即$ans(k+1)=ans(k)+1$,这与$cnt$的增加规律导致的结果是一致的，即$cnt(k+1)=cnt(k)+1=ans(k)+1=ans(k+1)$
对于$(k+1).l<=ed$显然不用增加点，有$cnt(k+1)=cnt(k)=ans(k)=ans(k+1)$

显然$cnt(1)=ans(1)$
故可证明对任意$n$，$cnt(n)=ans(n)$