核心概述
区间覆盖关注在给定区间集合下以最少数量或最优代价覆盖目标区间，常用贪心或DP并可结合区间树优化查询与更新。
原文引述
Description: Select minimum number of intervals to cover a target interval, or weighted cover with min/max total weight. Solved via greedy, DP, or interval tree.（摘自本节点现有英文注释） Time: Greedy O(n log n); DP O(n^2); Interval tree O(n log n) per query（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）
展开阐述
-
定义与背景
- 给定一组半开区间 [l, r)，目标是在区间族中选择若干区间覆盖目标区间 [L, R)。
- 变体包括：无权最少覆盖、加权最优覆盖（最小/最大权重和）、动态覆盖（区间可增删并需在线回答覆盖相关查询）。
-
接口/字段/语义（依仓库约定）
- 输入：区间集合 S 与目标区间 [L, R)；加权情形还含 cost。
- 输出：无权场景返回最少区间数；加权场景返回最优代价；动态场景支持插入/删除及查询操作。
- 统一采用左闭右开的端点语义避免边界歧义。
-
核心流程与关键要点
- 无权最少覆盖（贪心）：
- 常见策略：按左端点升序、同左端点按右端点降序排序；在当前可达范围内选右端点最远的区间，更新“当前已覆盖最远端”直到跨过 R。
- 正确性要点：局部最优（扩展最远）不妨碍后续可行性。
- 加权覆盖（DP）：
- 位置化DP：可将端点离散化，设 dp[x] 为覆盖到位置 x 的最小代价，转移形如 dp[r] = min(dp[r], dp[l] + cost)。
- 复杂度 O(n^2)；配合数据结构可将区间转移批量化。
- 区间树优化：
- 在线维护时，可在节点存储与位置相关的最优覆盖代价或辅助信息；对 [l, r) 做区间更新，对查询点/前缀做最优值查询，实现 O(n log n) 级别维护。
- 边界与一致性：
- 端点规范统一为 [l, r)；空覆盖或不可达需返回特定标记（如 INF/不可达）。
- 无权最少覆盖（贪心）：
-
复杂度与边界条件
- 贪心：排序 O(n log n)，扫描 O(n)。
- DP：朴素 O(n^2)；结合线段树/有序结构可优化到 O(n log n)。
- 动态维护：每次增删/查询期望 O(log n) 量级，视实现而定。
-
应用场景与扩展
- 最少设备/任务覆盖时间窗；字符串位置段的最少替换/覆盖操作；几何中线段覆盖与扫描线过程。
- 可与区间容器组合，实现区间并、相交检测与覆盖问题的整合处理。