算法基础之区间覆盖

区间覆盖

• 核心思想： 贪心

  • 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;
      }