526互联

贪心区间覆盖

发布时间 2024-01-08 22:02:58作者: TomLove

贪心区间覆盖

image-20240108215441577

算法分析

image-20240108215728871

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int n;
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    
    for(int i = 0; i < n; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }
    
    sort(range, range + n);
    
    int res = 0;
    bool success = false;
    for(int i = 0; i < n; i++)
    {
        int j = i, r = -2e9;
        while(j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++ ;
        }
        
        // 无解
        // 不能从所有区间的左端点中选到区间的右端点包含 目标区间的 ed
        if(r < st)
        { // 循环 区间左端点比目标区间靠左的区间后得到的最右侧端点比目标区间的 st 小
            res = -1;
            break;
        }
        
        // 执行到这里说明 所有能包含当前目标区间的 st 的区间中 右侧端点最靠右的区间
        // 找到了一个 能够包含目标区间左侧端点的并且区间右端点最靠右的 区间
        res ++ ;
        
        // 若果所选区间的右端点可以包含 目标区间的  ed 则直接跳出
        // 当前所选区间的个数便是最优解
        if(r >= ed)
        {
            success = true;
            break;
        }
        
        // 所选区间的最右侧的不能包含目标区间的右短点
        st = r;
        i = j - 1;  // 这里的 j 要 -1  是因为在上面 while 循环李最后 j++ 但是没有执行
    }
    
    if(!success) res = -1;
    printf("%d\n", res);
    
    return 0;
}