区间覆盖

用最少的给定区间覆盖目标区间;按左端点排序,每次选择能接上且右端点最远的区间。

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

题目描述

给定目标区间 [𝐿,𝑅] 和 𝑛 个可用区间 [𝑙𝑖,𝑟𝑖]。选择尽量少的可用区间,使它们的并集覆盖 [𝐿,𝑅]。无解输出 −1。

端点相接视为可以连续覆盖。

1≤𝑛≤2×105。

题解

按左端点 𝑙𝑖 升序排序。维护当前已经覆盖到的右端点 𝑐,初始 𝑐=𝐿,答案计数为 0。

当 𝑐<𝑅 时:

  • 扫描所有满足 𝑙𝑖≤𝑐 且尚未扫描过的区间,取其中最大的右端点 𝐹;
  • 若 𝐹≤𝑐,说明无法继续向右覆盖,输出 −1;
  • 否则选择这个区间,答案加一,令 𝑐=𝐹。

正确性:当前已经覆盖 [𝐿,𝑐],任何覆盖方案下一步都必须选择一个左端点不超过 𝑐 的区间。在这些区间中,右端点最远者能覆盖最多后续位置;用它替换任意其他选择不会使方案变差。因此每一步选择都是安全的。

复杂度

排序为 𝑂(𝑛log𝑛),每个区间只被扫描一次,总时间为 𝑂(𝑛log𝑛),空间为 𝑂(𝑛)。

参考

源码位置