![[贪心策略] 区间覆盖问题的双指针扫描与最优性证明](http://pic.xiahunao.cn/yaotu/[贪心策略] 区间覆盖问题的双指针扫描与最优性证明)
1. 区间覆盖问题与贪心策略第一次接触区间覆盖问题时我被它的简洁描述所吸引给定一个目标区间和若干候选区间如何用最少的候选区间完整覆盖目标区间这就像用不同长度的木板拼接成指定长度的围栏既要确保没有缝隙又要尽可能节省材料。贪心算法在这个问题上展现出惊人的效率。它的核心思想是每次选择能覆盖当前起点且右端点最远的区间。这种策略之所以有效是因为选择覆盖范围更广的区间能为后续选择留出更多空间。就像玩俄罗斯方块时我们会优先放置能消除最多行的方块。实际应用中这种算法可以优化视频广告投放用最少广告片段覆盖整个节目时段或课程安排用最少时间段覆盖所有教学内容。我曾用类似思路解决过服务器日志分析问题需要从海量时间片段中提取关键事件序列。2. 双指针扫描的实现细节实现这个算法时双指针技巧是关键。左指针标记当前覆盖终点右指针寻找最优区间。具体操作就像用探照灯扫描def interval_cover(target, intervals): intervals.sort(keylambda x: x[0]) # 按左端点排序 res 0 cur_end target[0] i 0 while i len(intervals): max_right -float(inf) # 双指针扫描能覆盖当前起点的区间 j i while j len(intervals) and intervals[j][0] cur_end: max_right max(max_right, intervals[j][1]) j 1 if max_right cur_end: # 无法继续覆盖 return -1 res 1 if max_right target[1]: # 已完全覆盖 return res cur_end max_right # 移动当前覆盖终点 i j - 1 # 关键跳过已处理区间最容易出错的点在于指针更新。我曾踩过这样的坑在找到一组候选区间后错误地将主指针直接跳到右指针位置ij这会导致跳过某些区间。正确的做法是ij-1因为循环末尾的i会自然推进到j的位置。3. 最优性证明的两种思路为什么贪心选择能得到最优解我们可以用两种方法证明构造性证明假设最优解使用k个区间贪心解使用m个区间。我们可以将贪心解的第一个区间与最优解的第一个区间比较。由于贪心选择的是右端点最远的区间完全可以用贪心的区间替换最优解的对应区间而不增加总数。依次类推最终证明mk。反证法示例假设存在比贪心解更优的解O找到第一个与贪心解不同的选择点此时O选择的区间右端点必然小于贪心选择将O的这个区间替换为贪心选择的区间新解仍然有效且区间数不变重复该操作直到与贪心解完全一致这就像拼图时如果有人声称用了更少的拼图块我们总能证明那些更优的方案要么有缺口要么实际使用了相同数量的拼图块。4. 常见变体与实战技巧区间问题在实际中有多种变体最典型的有最大不相交区间选择最多互不重叠的区间按右端点排序区间选点问题用最少的点覆盖所有区间同样按右端点排序重叠区间合并合并所有相交的区间按左端点排序后比较相邻区间处理这类问题时我有几个实用心得排序策略决定算法方向左端点排序常用于覆盖问题右端点排序适合选择问题边界条件要特别注意区间开闭、端点相等的情况需要单独处理使用哨兵值简化代码在目标区间两端添加虚拟区间可以减少特殊判断比如在LeetCode 452用最少数量的箭引爆气球中将问题转化为最大不相交区间问题后解题效率能从O(n²)提升到O(nlogn)。
1. 区间覆盖问题与贪心策略第一次接触区间覆盖问题时我被它的简洁描述所吸引给定一个目标区间和若干候选区间如何用最少的候选区间完整覆盖目标区间这就像用不同长度的木板拼接成指定长度的围栏既要确保没有缝隙又要尽可能节省材料。贪心算法在这个问题上展现出惊人的效率。它的核心思想是每次选择能覆盖当前起点且右端点最远的区间。这种策略之所以有效是因为选择覆盖范围更广的区间能为后续选择留出更多空间。就像玩俄罗斯方块时我们会优先放置能消除最多行的方块。实际应用中这种算法可以优化视频广告投放用最少广告片段覆盖整个节目时段或课程安排用最少时间段覆盖所有教学内容。我曾用类似思路解决过服务器日志分析问题需要从海量时间片段中提取关键事件序列。2. 双指针扫描的实现细节实现这个算法时双指针技巧是关键。左指针标记当前覆盖终点右指针寻找最优区间。具体操作就像用探照灯扫描def interval_cover(target, intervals): intervals.sort(keylambda x: x[0]) # 按左端点排序 res 0 cur_end target[0] i 0 while i len(intervals): max_right -float(inf) # 双指针扫描能覆盖当前起点的区间 j i while j len(intervals) and intervals[j][0] cur_end: max_right max(max_right, intervals[j][1]) j 1 if max_right cur_end: # 无法继续覆盖 return -1 res 1 if max_right target[1]: # 已完全覆盖 return res cur_end max_right # 移动当前覆盖终点 i j - 1 # 关键跳过已处理区间最容易出错的点在于指针更新。我曾踩过这样的坑在找到一组候选区间后错误地将主指针直接跳到右指针位置ij这会导致跳过某些区间。正确的做法是ij-1因为循环末尾的i会自然推进到j的位置。3. 最优性证明的两种思路为什么贪心选择能得到最优解我们可以用两种方法证明构造性证明假设最优解使用k个区间贪心解使用m个区间。我们可以将贪心解的第一个区间与最优解的第一个区间比较。由于贪心选择的是右端点最远的区间完全可以用贪心的区间替换最优解的对应区间而不增加总数。依次类推最终证明mk。反证法示例假设存在比贪心解更优的解O找到第一个与贪心解不同的选择点此时O选择的区间右端点必然小于贪心选择将O的这个区间替换为贪心选择的区间新解仍然有效且区间数不变重复该操作直到与贪心解完全一致这就像拼图时如果有人声称用了更少的拼图块我们总能证明那些更优的方案要么有缺口要么实际使用了相同数量的拼图块。4. 常见变体与实战技巧区间问题在实际中有多种变体最典型的有最大不相交区间选择最多互不重叠的区间按右端点排序区间选点问题用最少的点覆盖所有区间同样按右端点排序重叠区间合并合并所有相交的区间按左端点排序后比较相邻区间处理这类问题时我有几个实用心得排序策略决定算法方向左端点排序常用于覆盖问题右端点排序适合选择问题边界条件要特别注意区间开闭、端点相等的情况需要单独处理使用哨兵值简化代码在目标区间两端添加虚拟区间可以减少特殊判断比如在LeetCode 452用最少数量的箭引爆气球中将问题转化为最大不相交区间问题后解题效率能从O(n²)提升到O(nlogn)。
