解法
閉区間 \([l,r]\) で考える． 貪欲法． 基本は \(l\) が小さい順に， \(l\) が等しい場合は，\(r\) が小さい順に処理する．
\(l\) が小さい順に \(r\) をストックしていき， 小さい \(r\) から使っていく． \(r\) 達を priority queue に入れておけば実現できる．
実装
\(x\) が今調べている座標． \(l\) が等しい場合は，\(r\) 達を全て候補に入れてから， 区間に対応する座標を割り当てる．
注意
Priority queue が空のときは削除できない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
bool solve(){
ll n; cin >> n;
rep(i,n){
ll l,r; cin >> l >> r;
p[i] = {l,r};
}
sort(all(p));
p.push_back({INFL, -1}); // r は何でも良い ... [*]
min_priority_queue<ll> rs;
ll x = -1;
for(auto [l,r]: p){
while(x < l && rs.size()){
if(x <= rs.top()) {
rs.pop();
x++;
}else{
return false;
}
}
x = l;
rs.push(r);
}
assert(rs.size() == 1); // [*] の rだけ残っている
return true;
}
int main() {
ll t; cin >> t;
rep(ti,t){
yesno(solve());
}
return 0;
}
