博客

题目：给出n条线段，以及最大长度m，问最少需要多少条才能覆盖1-m这个区间，当无法全部覆盖的时候输出-1

思路：典型的区间覆盖问题，而且关键在于线段右端点上。虽然想到这一点，但是对于边界处理起来，还是有点复杂，可能会漏掉一些情况，大致分为以下几种情况，最后一种是对不满足线段的判定，主要我是用了两个点temp1和temp2对其进行维护，temp1表示最后一次选取的右端点，temp2则对左端点在temp1以内的点进行处理

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
	int l,r;
}line[25005];
int n,ans,len,cou;
int cmp(const void *a,const void *b){
	if(((node *)a)->l!=((node *)b)->l)
		return ((node *)a)->l-((node *)b)->l;
	else return ((node *)b)->r-((node *)a)->r;
}
int main(void){
	while(~scanf("%d%d",&n,&len)){
		int l,r;
		ans=cou=0;
		for(int i=1;i<=n;i++){
			scanf("%d%d",&l,&r);
			if(r<1||l>len)
				continue;
			line[cou].l=(l>1)?l:1;
			line[cou].r=(r>len)?len:r;
			cou++;
		}
		qsort(line,cou,sizeof(line[0]),cmp);
		int temp1,temp2;
		temp1=temp2=0;
		int flag=1;
		for(int i=0;i<cou;i++){
			if(line[i].r<=temp2)
				continue;
			else if(line[i].l<=temp1)
				temp2=max(temp2,line[i].r);
			else if(line[i].l>temp1){
				if(line[i].l==temp1+1){
					ans++;
					temp1=temp2=line[i].r;
				}
				else if(line[i].l<=temp2){
					ans++;
					temp1=temp2;
					temp2=max(temp2,line[i].r);
				}
				else if(line[i].l==temp2+1){
					ans++;
					if(temp1!=temp2)
						ans++;
					temp1=temp2=line[i].r;
				}
				else {
					flag=0;
					break;
				}
			}
			
		}
		if(flag==0)
			printf("-1\n");
		else {
			if(temp1!=temp2)
				ans++;
			if(temp2==len)
				printf("%d\n",ans);
			else printf("-1\n");
		}
	}
	return 0;
}