CJTX07｜区间标记计划 题解

核心算法

按右端点排序；若当前区间标记不足，就从右向左补选尚未使用的位置。

思路推导

将所有要求按右端点从小到大处理。对于区间 $[l,r]$：

1. 统计其中已有标记数 have；
2. 若 have<c，还需补放 c-have 个标记；
3. 从 $r$ 向 $l$ 扫描，优先选择最靠右的未标记位置。

正确性说明

用归纳法考虑一个包含“此前全部贪心选择”的最优方案。处理到右端点为 $r$ 的要求时，此前要求已经由这些固定选择满足。若当前仍缺少标记，设该最优方案另外选择了更靠左的位置 $x$，而贪心选择了更靠右且尚未固定的位置 $y$。把 $x$ 换成 $y$ 后，此前固定的贪心标记没有减少，当前要求仍满足；对尚未处理且右端点不小于 $r$ 的区间，靠右的 $y$ 也不会比 $x$ 更早失去作用。逐次交换后，仍存在一个最优方案包含本轮全部贪心选择，归纳成立。

复杂度

• 时间复杂度：$O(nm)$；
• 空间复杂度：$O(m)$。

在 $m,n\le5000$ 时最多约 $2.5\times10^7$ 次基础检查，可以通过。

易错点

• 必须按右端点排序；
• 补放时应从右向左，而不是从左向右；
• 统计时不要重复选择同一位置；
• 闭区间两端都要计入。