箱の番号の昇順に入れるボールを決定していく、以下のようなシミュレーションを考えます。

• 全ての \(1\) 以上 \(10^9\) 以下の整数 \(i\) に対して、以下の操作を行う。
  • (A) \(L_j=i\) である全ての整数 \(j\) について、ボール \(j\) を「箱に入れてもいいボールのリスト」に入れる。
  • (B)「箱に入れてもいいボールのリスト」から、ボールをどれか \(1\) つ決め、これを \(k\) とする。ボール \(k\) を箱 \(i\) に入れ、リストからボール \(k\) を削除する。
  • (C) 「箱に入れてもいいボールのリスト」に \(R_j \le i\) なるボールが残っていれば、ボールを全て入れることはできない。
• \(i=10^9\) まで操作を行い、全てのボールが箱に入っていれば、それが条件を満たすボールの入れ方である。

では、このシミュレーションの (B) の部分は、どう決めれば最適でしょうか?

実は、リストに残っているボールのうち \(R_j\) が最小であるボール \(j\) を箱に入れると必ず最適にボールを箱に入れることができます。なぜなら、 \(R_j\) が最小でないボールを箱に入れた時と比べて、その後の (C) の部分の条件が厳しくなることはないからです。

「 \(R_j\) が最小であるボールを \(1\) つ選んで取り出す」という操作は、 priority_queue などを使うと実現可能です。また、この問題では実際に箱への入れ方を求める必要はないので、ボールをリストに追加する際に \(R_j\) の値だけを管理すればよいです。

また、冒頭のシミュレーションを愚直に行うと TLE してしまいますが、「リストが空になったタイミングで、次に (A) の操作によってリストが空でなくなるタイミングまで \(i\) を飛ばす」という改善によってこれを免れることが可能です。これには set を用いる、もしくは予めソートされた \(L\) の配列を二分探索する という方法があります。

以上より、この問題を時間計算量 \(O(N \log N)\) 程度で解くことが出来ました。

#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;
using pi=pair<int,int>;

int main(){
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n;
    cin >> n;
    vector<pi> seg(n);
    map<int,vector<int>> g;
    set<int> st;
    for(int i=0;i<n;i++){
      cin >> seg[i].first >> seg[i].second;
      g[seg[i].first].push_back(seg[i].second);
      st.insert(seg[i].first);
    }
    st.insert(inf);
    int i=(*st.begin());
    priority_queue<int,vector<int>,greater<int>> pq;
    bool fl=true;
    while(i<=1000000000){
      for(auto &nx : g[i]){pq.push(nx);}
      int od=pq.top();
      pq.pop();
      if(pq.empty()){i=(*st.lower_bound(i+1));}
      else{
        if(pq.top()<=i){fl=false;break;}
        i++;
      }
    }
    if(!pq.empty()){fl=false;}
    if(fl){cout << "Yes\n";}else{cout << "No\n";}
  }
  return 0;
}