Consider the following simulation of determining the balls to put in the increasing order of the box’s indices.

• For every integer \(i\) between \(1\) and \(10^9\) (inclusive), perform the following operations.
  • (A) For every integer \(j\) such that \(L_j=i\), add Ball \(j\) to “the list of balls that may be put into a box.”
  • (B) Choose one ball from “the list of balls that may be put into a box,” calling it \(k\). Put Ball \(k\) into Box \(i\) and remove Ball \(k\) from the list.
  • (C) If a ball such that \(R_j \le i\) remains in “the list of balls that may be put into a box,” then it is impossible to put all the balls into the boxes.
• After repeating it up to \(i=10^9\), if all the balls are in the boxes, then that assignments of balls satisfy the conditions.

Now, what is the optimal strategy of step (B) in the simulation?

In fact, if we put the Ball \(j\) with minimum \(R_j\), we can always put the balls optimally. This is because the conditions in step (C) does not become stricter than when putting a ball whose \(R_j\) is not minimum.

The operation of “choosing a ball with minimum \(R_j\)” can be fulfilled by data structures like priority_queue. Also, as we do not have to find the actual assignment to boxes, it is sufficient to manage just the value of \(R_j\) when adding a ball into the list.

Although doing the simulation described above naively will lead to TLE, it can be avoided by the improvement in which “once the list becomes empty, skip \(i\) to the next value that the list becomes non-empty by the operation (A).” To do so, one can use a set, or perform a binary search against the array of \(L\) sorted beforehand.

Therefore, we could solve the problem in a total time complexity of \(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;
}