区间点覆盖

选择最少的点,使每个区间至少包含一个点;按右端点排序,在未覆盖区间的右端点放点。

标签 贪心 / 区间 / 点覆盖 / 排序

题目描述

给定 𝑛 个区间 [𝑙𝑖,𝑟𝑖]。选择尽量少的点,使每个区间至少包含一个选中的点。

点可以选在任意实数位置,区间为闭区间。

题解

按右端点 𝑟𝑖 升序排序。维护最后放下的点 𝑝,初始为 −∞。

依次扫描每个区间:

  • 若 𝑙𝑖≤𝑝≤𝑟𝑖,该区间已经包含 𝑝,跳过;
  • 否则在 𝑟𝑖 放一个新的点,令 𝑝=𝑟𝑖,答案加一。

因为右端点有序,若 𝑙𝑖≤𝑝,必有 𝑝≤𝑟𝑖,所以只需判断 𝑙𝑖≤𝑝。

正确性:取当前尚未被覆盖的区间中右端点最小的一个 [𝑙,𝑟]。任何覆盖它的点都满足 𝑥≤𝑟。把该点换成 𝑟,对右端点不小于 𝑟 的后续区间仍然有效,因此不会让方案变差。重复即可。

复杂度

排序为 𝑂(𝑛log𝑛),扫描为 𝑂(𝑛)。只统计点数时空间为 𝑂(𝑛)(保存区间);若需要输出所有点,额外空间为 𝑂(𝑛)。

参考

源码位置