本文共 909 字，大约阅读时间需要 3 分钟。

最近在学习算法，c++还有好多知识不会，想慢慢通过算法来熟悉，如果有题讲解的不好或是代码写的不好还请大家多多指教。

题意：给你N头牛和工作的时间区域T（1~T），每头牛都有工作的开始时间和结束时间，代码里分别用cows[i].begin和cows[i].end表示，选择尽可能少的奶牛完成清洁工作，如果不可能分配的话，打印-1

思路：这道题是一个区间贪心的问题，对给的牛工作时间进行排序，开始时间小的排在前面，开始时间一样的，结束时间小的排在前面。然后进行贪心

误区：3 10

           1 5

            6 10

            10 10

这个最后的结果是2，而不是-1.它可以是连续的（1~6）（6~10），也可以是（1~5）（6~10），所以每回与上个数比较的时候是与（结束时间+1）进行比较而不是与上一个结束时间比较

#include
    
     #include
     
      using namespace std;const int N_max=25100;struct times{	int begin,end;}cows[N_max];bool cmp(times a,times b){	if(a.begin==b.begin)		return a.end
      
       >cows[i].begin>>cows[i].end;		}		sort(cows+1,cows+1+N,cmp);		if(cows[1].begin!=1){			cout<<"-1\n"<
       
        cows[id].end+1)					break;				if(cows[j].begin>=cows[id].begin&&cows[j].end>=cows[id].end+1){					if(cows[j].end>cows[cnt].end)						cnt=j;				}			}			if(cnt==0)				i++;			else{				id=cnt;				ans++;				i=id;			}		}		if(cows[id].end==T)			cout<
        
         <
         
        
       
      
     
    

转载地址：http://xkxhj.baihongyu.com/