自动搬运

查看原文

来自洛谷，原作者为

	takanashi_mifuru 一往无前，披星戴月，勿要回首 | 会いたい愛が痛いアイロニー | 时在今日，天下当倾 | 「私が毒を毒づくのは 毒が好きだったってわけさ」

搬运于2025-08-24 23:01:18，当前版本为作者最后更新于2024-07-22 07:54:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易发现这个区间交就两个信息比较有用，一个是右端点的最小值，另一个是左端点的最大值。

那我们按照右端点从小到大排序，然后就能确定右端点的最小值在哪了，而如果一个区间如果取走之后可用就直接拿走，否则就直接不要，这样就是对的。

为什么？

首先因为这个点和前面不匹配，所以这个必须要选，而一个区间能不能被当作一个匹配的区间这件事情具有单调性因为右端点单调不降，所以左端点的限制只会越来越宽，不存在前面能用后面开了新段就没法用的段，所以没问题。

$w=0$ 要特判。

#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;
}