最小区间覆盖问题

给你一段区间1~t，有n个区间，求能覆盖完1~t的区间的最小个数，如果不能覆盖完输出-1

例题：poj2376

我们先假设已经覆盖了区间a~b，那么我们选择下一个区间的时候，为了保证最贪心的取，肯定会取左端点>=b+1的区间，这样重叠浪费的就少

然后我们再按贪心的思想，肯定是右端点越长覆盖的越多

那么我们现在开始思考这个问题

先按左端点从小到大排序，如果左端点相同的话按右端点从左到右排序

然后我们先判断第一个区间

如果第一个区间的左端点大于1 的话说明不能覆盖完1~t，直接输出-1

否则的话，last表示已经覆盖的区间的下标，我们把最原始的区间的下标last设为1，记录区间个数的变量flag设为1

然后我们从i=2开始遍历，当第i个区间的左端点<=last的右端点+1，并且第i个区间的右端点大于last的右端点的话，我们就从i开始找右端点最长的区间

找到之后个数++，i变化一下

最后判断一下已覆盖的区间last的右端点是否大于等于t，如果是就输出个数，如果不是说明没有覆盖完全，输出-1

/*
 .----------------.  .----------------.  .----------------.  .----------------. 
| .--------------. || .--------------. || .--------------. || .--------------. |
| |  ________    | || |  _________   | || | ____    ____ | || |     ____     | |
| | |_   ___ `.  | || | |_   ___  |  | || ||_   \  /   _|| || |   .'    `.   | |
| |   | |   `. \ | || |   | |_  \_|  | || |  |   \/   |  | || |  /  .--.  \  | |
| |   | |    | | | || |   |  _|  _   | || |  | |\  /| |  | || |  | |    | |  | |
| |  _| |___.' / | || |  _| |___/ |  | || | _| |_\/_| |_ | || |  \  `--'  /  | |
| | |________.'  | || | |_________|  | || ||_____||_____|| || |   `.____.'   | |
| |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
#define lowbit(x) x&(-x)
#define PI 3.1415926535
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int b){
	return b>0 ? gcd(b,a%b):a;
}
const int N=25000+10;
 
/*
int dx[8]={-2,-2,-1,1,2,2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int dx[8]={-1,1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
*/
 
struct name{
	int l,r;
}q[N];
int n;
bool cmp(name a,name b){
	if(a.l !=b.l )return a.l <=b.l ;
	return a.r <=b.r ;
}
void sove(){
	int t;
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>q[i].l >>q[i].r ;
	}
	sort(q+1,q+1+n,cmp);
	if(q[1].l >1){
		cout<<-1<
		return ;
	}
	int flag=1,last=1;
	for(int i=2;i<=n;i++){
		if(q[i].l <=q[last].r +1&&q[i].r >q[last].r ){
			int j=i;
			while(q[i].l <=q[last].r +1&&i<=n){
				if(q[i].r >q[j].r ){
					j=i;
				}
				i++;
			}
			i=j;
			last=j;
			flag++;
			if(q[last].r >=t)break;
		}
	}
	if(q[last].r 
		cout<<-1<
	}else cout<
}
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie() ,cout.tie() ;
	int t=1;
//	cin>>t;
	while(t--){
		sove();
	}
	return 0;
}