算法基础之区间覆盖

2024-01-08 07:20:15

区间覆盖

  • 核心思想: 贪心

    • 1.将所有区间按照左端点大小排序

    • 2.遍历所有区间 找到能覆盖start右端点最大的那个区间(双指针)

    • 3.更新start为max?

    •   #include<iostream>
        #include<algorithm>
        #include<cstring>
        
        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 st,ed;
            cin>>st>>ed>>n;    
            for(int i=0;i<n;i++) cin>>range[i].l>>range[i].r;
            
            sort(range,range+n);
            int res=0;
            bool success = false;  //标记是否找出能覆盖的区间
            for(int i=0;i<n;)  //双指针 用里层j去更新i
            {
                int j=i,r=-2e9;  //r为最大右端点
                while(j<n && range[j].l <= st)  //能覆盖st
                {
                    r = max(r,range[j++].r);  //且右端点最大
                }
                
                if(r < st) break;  //遍历全部 右端点小于st 说明没有能覆盖的
                
                res++;  //有能覆盖的 res++
                
                if (r>=ed)  //找到答案
                {
                    success = true;
                    break;
                }
                 
                st = r;  //更新st为当前最大右端点
                i = j;  //从j开始继续
            }
            
            if(!success) res = -1;
            cout<<res;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135396357
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。