区间覆盖问题——贪心经典应用

这道题是区间覆盖的板子题，目标是选最少的闭区间把 [0, L] 完全盖住。贪心策略很直接：每次在能接上的区间里，挑右端点最远的那个，这样“一步跨得最远”，后面需要的区间数自然就少。

题目简述

有 N 条闭区间 [l_i, r_i]，问能否用其中若干条覆盖 [0, L]，若能，输出最少需要几条；否则输出 -1。

思路分析

1. 为什么用贪心？

我们要覆盖的起点是 0。第一步，所有左端点 <= 0 的区间都可以作为“第一段”，显然选右端点最大的那一条最优——它让已覆盖的右边界变得最大，后续选择余地也最大。

之后每一步都面临同样的局面：假设当前已经覆盖到 cur，那么所有左端点 <= cur 的区间都能和现有覆盖“接上”（因为闭区间，端点重合也算覆盖），从中挑一个右端点最大的区间，就能让 cur 膨胀得最快。

这种“每次选当前最优”的策略在区间覆盖问题中是全局最优的，因为区间之间没有相互依赖，只关心右端点的延伸能力。

2. 算法流程

• 将区间按左端点从小到大排序。
• 初始化 cur = 0，ans = 0，指针 i = 1。
• 只要 cur < L，就做一轮选择：
  1. 用指针 i 扫描所有左端点 <= cur 的区间，记录其中最大的右端点 maxR。
  2. 如果 maxR == cur，说明没有任何区间能向右延伸，覆盖失败，输出 -1。
  3. 否则，cur = maxR，ans++。
• 循环结束后输出 ans。

细节处理

• L = 0：目标区间为空，不需要任何线段，直接输出 0。
• 闭区间连接：条件必须是 l_i <= cur，不能是 <，否则像 [0,5] 和 [5,10] 这种刚好在端点相接的情况会被漏掉。
• 数组大小：N 最大 1e5，数组开 2e5 更保险。
• 排序：默认按左端点升序即可，若左端点相同，右端点顺序无所谓。
• 指针移动：每轮扫描过的区间就不再重复扫描，因为 cur 只会增大，之前左端点 <= 旧 cur 的区间下次肯定仍然满足 <= 新 cur，无需回头。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
const int N=1e5+10;
int n,L;
int cur,ans;
struct qj{
    int l,r;
}a[N];
bool cmp(qj a,qj b){
    return a.l<b.l;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>L;
    for(int i=1;i<=n;i++){ 
        cin>>a[i].l>>a[i].r;
    }
    if(L==0){
        cout<<0;
        return 0;
    }
    sort(a+1,a+n+1,cmp);
    int idx=1;
    while(cur<L){
        int mxr=cur;
        while(idx<=n&&a[idx].l<=cur){
            mxr=max(a[idx].r,mxr);
            idx++;
        }
        if(mxr==cur){
            cout<<-1;
            return 0;
        }
        cur=mxr;
        ans++;
    }
    cout<<ans;
    return 0;
}

结语

贪心算法的核心在于证明“局部最优”能导出“全局最优”。这道题代码虽短，但边界条件（尤其是 L=0 和 <= 的判断）容易出错，写的时候多留个心眼。掌握了这个模型，很多变形题（如区间合并、最少线段覆盖）都能迎刃而解。