题目描述
给定 个区间 。选择尽量少的点,使每个区间至少包含一个选中的点。
点可以选在任意实数位置,区间为闭区间。
题解
按右端点 升序排序。维护最后放下的点 ,初始为 。
依次扫描每个区间:
- 若 ,该区间已经包含 ,跳过;
- 否则在 放一个新的点,令 ,答案加一。
因为右端点有序,若 ,必有 ,所以只需判断 。
正确性:取当前尚未被覆盖的区间中右端点最小的一个 。任何覆盖它的点都满足 。把该点换成 ,对右端点不小于 的后续区间仍然有效,因此不会让方案变差。重复即可。
复杂度
排序为 ,扫描为 。只统计点数时空间为 (保存区间);若需要输出所有点,额外空间为 。
参考