Reliauk又手刃了一道黑题
takanashi_mifuru
·
·
题解
容易发现这个区间交就两个信息比较有用，一个是右端点的最小值，另一个是左端点的最大值。
那我们按照右端点从小到大排序，然后就能确定右端点的最小值在哪了，而如果一个区间如果取走之后可用就直接拿走，否则就直接不要，这样就是对的。
为什么？
首先因为这个点和前面不匹配，所以这个必须要选，而一个区间能不能被当作一个匹配的区间这件事情具有单调性因为右端点单调不降，所以左端点的限制只会越来越宽，不存在前面能用后面开了新段就没法用的段，所以没问题。
```cpp
#include<bits/stdc++.h>
using namespace std;
int T;
int n,w;
struct node{
int lt,rt;
bool friend operator < (const node &a,const node &b){
return a.rt<b.rt;
}
}A[200005];
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&w);
bool tag=true;
for(int i=1;i<=n;i++){
scanf("%d%d",&A[i].lt,&A[i].rt);
if(A[i].rt-A[i].lt+1<w)tag=false;
}
if(!tag){
puts("No");
continue;
}
if(!w){
puts("1");
continue;
}
sort(A+1,A+1+n);
int Max=-1;
int pos=0;
for(int i=1;i<=n;i++){
if(Max<A[i].lt){
pos++;
Max=A[i].rt-w+1;
}
}
printf("%d\n",pos);
}
return 0;
}
```