区间覆盖问题的贪心模型详解

wflengxuenong · 2025-10-10 08:22:33 · 个人记录

1. 区间覆盖问题的基本模型

模型一：选择不相交区间（最大不相交区间数）

问题描述：给定n个区间，选择尽可能多的区间，使得这些区间互不相交。

贪心策略：按区间的右端点从小到大排序

算法步骤：

1. 将所有区间按右端点从小到大排序
2. 初始化：count = 0, last_end = -∞
3. 遍历每个区间[l, r]：
   - 如果 l >= last_end：
     - count++
     - last_end = r
4. 返回count

证明思路：

• 选择右端点最小的区间可以为后续留下更多空间
• 任何最优解都可以通过替换变成贪心解

习题：

P1803 凌乱的yyy / 线段覆盖

模型二：区间完全覆盖

问题描述：用最少的区间覆盖指定的线段[L, R]

贪心策略：按左端点排序，每次选择能覆盖当前起点且右端点最大的区间

算法步骤：

1. 按左端点从小到大排序
2. 初始化：count = 0, current = L, i = 0
3. while current < R:
   - 在左端点<=current的区间中，选择右端点最大的
   - 如果找不到这样的区间：返回-1（无法覆盖）
   - count++, current = max_right
   - 如果current >= R: 返回count

习题：

• [POJ 2376] Cleaning Shifts UVa 10382 /LOJ10002 https://loj.ac/p/10002

模型三：区间点覆盖（用最少的点覆盖所有区间）

问题描述：用最少的点，使得每个区间至少包含一个点

贪心策略：按右端点排序，在右端点处放点

算法步骤：

1. 按右端点从小到大排序
2. 初始化：count = 0, point = -∞
3. 遍历每个区间[l, r]：
   - 如果 l > point：
     - count++
     - point = r
4. 返回count

证明思路：

• 在右端点放点可以覆盖尽可能多的后续区间

习题：

• [LeetCode 452] 用最少数量的箭引爆气球
• [USACO] 区间点覆盖

例题代码：

// LeetCode 452. 用最少数量的箭引爆气球
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;

        sort(points.begin(), points.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[1] < b[1];
             });

        int arrows = 1;
        int arrow_pos = points[0][1];

        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > arrow_pos) {
                arrows++;
                arrow_pos = points[i][1];
            }
        }

        return arrows;
    }
};

模型四：区间分组（最小分组数）

问题描述：将区间分成若干组，每组内区间互不相交，求最少组数

贪心策略：按左端点排序，用小根堆维护每组的最大右端点

算法步骤：

1. 按左端点从小到大排序
2. 初始化小根堆（存储每组的最大右端点）
3. 遍历每个区间[l, r]：
   - 如果堆为空或堆顶 > l：
     - 新开一组，将r加入堆
   - 否则：
     - 更新堆顶为r（将该区间加入堆顶对应的组）
4. 返回堆的大小

习题： P2859 [USACO06FEB] Stall Reservations S

• P7913 [CSP-S 2021] 廊桥分配
• [LeetCode 253] 会议室 II

2. 经典竞赛真题

真题1：[POJ 1328] Radar Installation

题目：在x轴上放置雷达，每个雷达覆盖半径为d，求覆盖所有岛屿的最少雷达数

转换：将岛屿位置转换为x轴上的覆盖区间

对于岛屿(x,y)，雷达能覆盖的x轴区间为：
[x - sqrt(d*d - y*y), x + sqrt(d*d - y*y)]

解法：区间点覆盖模型

真题2：P2859 [USACO06FEB] Stall Reservations S

题目：n头奶牛，每头有挤奶时间区间，求最少牛栏数

解法：区间分组模型

3. 进阶变形问题

变形1：带权区间调度

问题：每个区间有权值，选择不相交区间使总权值最大

解法：DP + 二分查找，不是纯贪心

• P2439 [SDOI2005] 阶梯教室设备利用

变形2：区间合并

问题：合并所有重叠区间 解法：按左端点排序后合并

• P2082 区间覆盖（加强版）

4. 练习题分类

基础练习

1. 选择不相交区间

   • [LeetCode 435] 无重叠区间
   • [HDU 2037] 今年暑假不AC

2. 区间完全覆盖

   • [POJ 2376] Cleaning Shifts
   • [LeetCode 1326] 灌溉花园的最少水龙头数目

3. 区间点覆盖

   • [LeetCode 452] 用最少数量的箭引爆气球
   • [POJ 1328] Radar Installation

4. 区间分组

   • [LeetCode 253] 会议室 II
   • [POJ 3190] Stall Reservations
   • AT_abc377_dMany Segments 2

进阶练习

1. [Codeforces 1029C] Maximal Intersection

   • 删除一个区间使剩余区间交集最大

2. [Atcoder ABC 103D] Robot Arms

   • 区间点覆盖的变形

3. [USACO 2014 Jan] Ski Course Rating

   • 并查集+贪心思想

4. [NOIP 2005] 校门外的树

   • 区间合并应用

5. 解题技巧总结

排序选择技巧

• 选择不相交区间：按右端点排序
• 区间完全覆盖：按左端点排序
• 区间点覆盖：按右端点排序
• 区间分组：按左端点排序

证明方法

1. 交换论证：证明贪心选择不会比最优解差
2. 归纳法：证明前k步都是最优的
3. 反证法：假设存在更优解，推导矛盾

调试技巧

• 画图理解区间关系
• 构造边界测试用例
• 与暴力解法对拍

通过系统练习这些模型，能够快速识别区间覆盖问题的类型并选择正确的贪心策略。记住核心思想：排序是贪心的前提，正确的排序方式决定了贪心策略的有效性。