贪心算法——区间覆盖问题

爱被打了一巴掌 2022-05-09 07:08 379阅读 0赞

## 区间覆盖问题 ##

数轴上有n个闭区间\[ai,bi\]，选择尽量少的区间覆盖一条指定的线段\[s,t\]。

## 分析： ##

把各区间按照a从小到大排序。如果区间1的起点不是s，无解，否则起点在s的最长区间。选择\[ai,bi\]后，新的起点设置成bi。直至覆盖整个线段。

![70][]

## 输入： ##

N:测试数据组数

begin，end：要覆盖区间的起始和终止点

n：区间数。后面跟随n个区间

## 输出： ##

覆盖的具体区间 以及 覆盖区间的总数

## 代码： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int maxn=20;
    
    struct timetable
    {
    	int a;
    	int b;
    }time[maxn];
    
    bool comp(timetable &x,timetable &y)//多看两遍 
    {
    		return (x.a<y.a);
    }
    
    
    
    int main()
    {
    	int i,j,N,n,count;
    	int begin,end;
    	while(cin>>N)//N表示有几组测试数据 
    	{
    		while(N--)
    		{
    			cin>>begin>>end;
    			cin>>n;//n个区间 
    			for(i=0;i<n;i++)
    			{
    				cin>>time[i].a;
    				cin>>time[i].b;
    			}
    			
    			sort(time,time+n,comp);//区间按照a从小到大排序 
    			
    			count=0;
    			int len=0,maxlen,tmp;
    			int newbegin=begin;
    			i=0; 
    			while(len<end-begin)
    			{
    				maxlen=0;
    				for(i;i<n;i++)//找当前begin情况下最长 
    			    {
    					if(time[i].a<=newbegin)
    					{
    						tmp=time[i].b-newbegin;
    						if(tmp>maxlen)
    						{
    							maxlen=tmp;
    							j=i;
    						}	
    					}
    					else
    						break;	
    				}
    				
    				if(maxlen==0)//说明断了，不存在连续覆盖 
    				{
    					cout<<"no exit;";
    					return 0;
    				}
    				
    				cout<<"("<<time[j].a<<","<<time[j].b<<")"<<"  ";
    				len+=maxlen;
    				count++;
    				newbegin=time[j].b;
    				
    			}
    			cout<<endl<<count<<endl; 
    		}
    	} 
    }

拓展阅读（挺好）：

[ACM知识点 之 贪心（5）最小区间覆盖问题][ACM_ _ _5]

[70]: /images/20220509/a4b324df3f7c42e7b736007b35f70e14.png
[ACM_ _ _5]: https://blog.csdn.net/xia842655187/article/details/51944829