この問題は区間スケジューリング問題そのものです。

つまり、終了時刻の昇順にソートした上で受け入れることができる予約を貪欲に受け入れることが最善です。

• Algorithm | 区間スケジューリング問題をPython3で解説（例題あり）
• 区間スケジューリング問題
• Wikipedia 英語版: Interval scheduling

実装例の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<pair<int,int>> vp(n);
  for(int i=0;i<n;i++){
    cin >> vp[i].second;
    cin >> vp[i].first;
  }
  sort(vp.begin(),vp.end());
  int lef=-1e9,res=0;
  for(auto &nx : vp){
    if(lef<=nx.second){
      res++;
      lef=nx.first;
    }
  }
  cout << res << "\n";
  return 0;
}