区间覆盖

image.png

image.png

这道题的本质——让我们找到给定区间中最能代表线段区间的区间，然后尽可能少。目的是可以完全代表这个线段区间。

解决方法：将所有的区间按照左端点从左到右进行排序。然后找到能够覆盖“目标区间”左边界的所有区间中，右边界最大的那个区间作为第一个。接下来，找能够覆盖刚刚确定的第一个区间右边界(其实也是整个的左边界)的所有区间中，右边界最大的那个区间作为下一个，依次这样下去即可。

C++代码

采用了双指针，看看以当前区间开始能否成功。
res ++不用判断，因为最后的输出是靠的success的状态。记得更新当前维护的最大值。
curpt——维护当前需要覆盖的点
rmax——找到所有能够覆盖的区间的右边界的最大值

• 提前终止
• 如果中间有缝隙，则不能success
  这两个判断不分先后的

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

int n;
int l, r;
int st, ed;
PII q[N];

int main()
{
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &l, &r);
        q[i] = {l, r};
    }
    sort(q, q + n);
    
    int res = 0;
    int rmax = -2e9;
    int curpt = st;
    bool success = false;
    for(int i = 0; i < n; i ++)
    {
        int j = i;
        while(j < n && q[j].first <= curpt)
        {
            rmax = max(rmax, q[j].second);
            j ++;
        }
        
        res ++;
        curpt = rmax;
        
        if(q[j].first > curpt) break;
        
        if(rmax >= ed)
        {
            success = true;
            break;
        }
        
        i = j - 1;
    }
    
    if(success) cout << res << endl;
    else cout << -1 << endl;
    
    return 0;
}