区间选点题解

思路

按照右端点从小到大考察区间。对于当前还没有被已选点覆盖的区间，选择它的右端点。这个点在不超出当前区间的前提下尽可能靠右，因此最有机会同时覆盖后续区间。

做法

先将所有区间按右端点升序排列。维护最近一次选择的点。依次扫描区间：如果最近选择的点已经位于当前区间内，就不需要新增点；否则选择当前区间的右端点，并把答案加一。

正确性证明

考虑按右端点排序后第一个尚未被覆盖的区间 $[L,R]$。任何合法方案都必须在该区间中选择至少一个点 $p$。把这个点替换为 $R$ 不会使已经处理的区间失去覆盖，因为此前区间已经由更早选择的点处理；对于尚未处理的任一区间，其右端点不小于 $R$，若它包含 $p$ 且与当前决策有关，则把点向右移动到 $R$ 仍不会越过该区间的右端点，并且 $R$ 不小于 $p$。因此总存在一个最优方案包含点 $R$。

选择 $R$ 后，所有包含它的区间都被覆盖，剩余问题与原问题形式相同。重复上述交换论证可知，每次选择当前未覆盖区间的右端点都能保留某个最优方案，最终所选点数最少。

复杂度

排序耗时 $O(n\log n)$，扫描耗时 $O(n)$，总时间复杂度为 $O(n\log n)$；存储区间的空间复杂度为 $O(n)$。