この問題は実は次のアルゴリズムによってパンチを放つ位置を決めていくのが最適です。

• まず、壁が存在する区間 \([L, R]\) の組を \(R\) に対して昇順にソートします。
• その後、ソートで得られた順番に壁を見ていき、壁が破壊されていない場合は右端にパンチを放って破壊していきます。

破壊する手順はより厳密に定式化すると次のようになります。 まず、最後にパンチした座標を \(x\) とします。( 1 度もパンチをしていない場合 \(x = -\infty\) です。) ここで、パンチの位置である右端を基準にソートを行ったことから、操作を経るにつれて \(x\) はだんだん大きくなっていく (単調増加) という性質があります。

壁をソート順に見ていったとき、R\(L\) が \(x + D - 1\) 以下であるかそうでないかによって場合分けを行います。( 12-03 23:08 修正しました)

• \(L\) が \(x + D - 1\) より大きい場合、 \(x\) の単調増加性と合わせるとこの壁は明らかに破壊されていないことが確認できます。そこで、 \(x = R\) として \([R, R + D - 1]\) にパンチします。
• \(L\) が \(x + D - 1\) 以下である場合は何もしません。なぜならば壁は最後のパンチによって破壊されているからです。

アルゴリズムの正当性の証明を行います。上記のアルゴリズムによって得られる答えを \(A\) として、「答えが \(A\) 以下である」という証明と「答えが \(A\) 以上である」という証明を行えば、この問題の答えが \(A\) であることを証明できます。
この \(2\) つの証明は以下のようにして行うことができます。

• (答えが \(A\) 以下であることの証明) : 今まで説明した手順によってすべての壁が破壊できているので、 \(A\) 回のパンチによって壁を破壊する方法が存在することがわかります。よって答えは \(A\) 以下です。
• (答えが \(A\) 以上であることの証明) : \(N\) 枚の壁の中から、アルゴリズムの操作中に「 \(R\) が \(x + D - 1\) より大きい場合」という条件分岐へ進んだ \(A\) 枚の壁のみを取り出します。この \(A\) 枚の壁からどの \(2\) 枚を取り出しても、間隔が \(D\) 以上離れているので、パンチによって同時に破壊することができません。よって、 \(2\) 枚以上同時に破壊できない壁が \(A\) 枚あることになるので、高橋君は最低でも \(A\) 回パンチする必要があるとわかります。よって答えは \(A\) 以上です。

よってこのアルゴリズムの正当性が確かめられました。
計算量はソートがボトルネックとなって \(\mathrm{O}(N \log N)\) となります。

ちなみにこの問題で使用されているアルゴリズムは「区間スケジューリング問題」と呼ばれる有名な問題と同じアルゴリズムです。

C++ による実装例は次の通りです。

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
  using ll = long long;
  using P = pair<ll, ll>;
  ll N, D, L, R;
  vector<P> LR;
  cin >> N >> D;
  for (int i = 0; i < N; i++) {
    cin >> L >> R;
    LR.emplace_back(L, R);
  }
  sort(begin(LR), end(LR), [](P& a, P& b) { return a.second < b.second; });
  ll ans = 0, x = -(1LL << 40);
  for (auto& [l, r] : LR) {
    if (x + D - 1 < l) ans++, x = r;
  }
  cout << ans << "\n";
}