一道贪心题。
我们可以将每一堵墙的右端点从小到大进行排序，然后我们从第 \(1\) 堵墙开始看，将在第 \(1\) 堵墙的右端点打破后会倒塌的墙全部跳过，去看下一堵还没被打破的墙。可以证明这是最优解。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, d, ans;
struct xvl_ {
int l, r;
bool operator < (const xvl_& s) const {
return r < s.r;
}
}a[200005];
signed main() {
ios :: sync_with_stdio(0);
cin >> n >> d;
for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ans++) {
int bk = i + 1;
while (a[bk].l <= a[i].r + d - 1 and bk <= n) bk++;
i = bk; // 前面的墙被打破了
}
cout << ans;
return 0;
}
/*
0 1 2 3 4 5 7 8 9 …
1 ---
2 -----
3 -------
0 1 2 3 4 5 7 8 9 …
1 ---
2 -----
3 ---------
*/