区间最大不相交问题题解

思路

若已经选择的最后一个区间右端点为 $x$，下一个区间必须满足左端点严格大于 $x$，因为题目中的区间是闭区间，共用端点也属于相交。

为了给后续区间留下尽可能大的空间，每次应在当前还能选择的区间中优先选择右端点最小的区间。

做法

将所有区间按右端点从小到大排序，右端点相同时按左端点排序。依次扫描排序后的区间，记录最近一次选择区间的右端点。若当前区间左端点严格大于该值，就选择当前区间并更新记录。

证明该贪心策略正确。考虑任意最优方案的第一个区间，设其右端点为 $r$；贪心选择的第一个区间右端点为 $r'\le r$。将最优方案的第一个区间替换为贪心区间后，最优方案中其余区间的左端点原本都严格大于 $r$，因而也严格大于 $r'$，替换不会产生相交且区间数量不变。对剩余区间重复应用同样的交换即可得到与贪心方案一致的最优方案。

复杂度

排序需要 $O(n\log n)$ 时间，扫描需要 $O(n)$ 时间，总时间复杂度为 $O(n\log n)$；空间复杂度为 $O(n)$。