[1] 答えが \(-1\) かどうかの判定

最初に、答えが \(-1\) かどうかの判定方法、すなわち何度でも点数を交換できるときに目標を達成できるかの判定方法について考えます。\(B_i\) の大きい人（つまり条件の厳しい人）から優先的に高い点数を割り当てていくことが最善であることを考えると、目標を達成できるための条件は次のようになります。

\(A,B\) をそれぞれ昇順にソートしたときに、任意の \(i\) について \(B_i \leq A_i\) が成り立つ。

最初にこの条件を思いついた人が多いとは思いますが、この問題を解く上ではもう少し条件を言い換える必要があります。

\(1 \leq t \leq 10^9\) に対し、

\(cnt_t=(B_i\leq t\) を満たす \(i\) の個数 \()-(A_i\leq t\) を満たす \(i\) の個数 \()\)

とおく。このとき、任意の \(t\) について \(cnt_t \geq 0\) が成り立つ。

上の \(2\) つの条件は同値です。

[2] 一度も点数を入れ替えなかった人の数の最大値を求める

最初の段階で、任意の \(i\) について \(B_i \leq A_i\) が成り立っている場合、答えは \(N\) です。

そうでない場合、点数を入れ替える人の集合 \(S\) を考え、\(|S|\) を最小化する方法を考えます。\(A_i<B_i\) であるような人 \(i\) は必ず \(S\) に含まれる必要があります。

なので、\(S\) を \(A_i<B_i\) であるような人からなる集合とし、任意の \(t\) について \(cnt_t \geq 0\) が成り立つまで他の人を一人ずつ \(S\) に追加していく方針をとることにします。

どの順番で人を追加していくのが最善なのでしょうか？

現時点で \(cnt_t < 0\) であるような最小の \(t\) を考えます。すると、\(B_i \leq t\) かつ \(t < A_i\) であるような人 \(i\) を追加する必要があります。そのような人が存在しなければ、目標は実現不可能です。そのような \(i\) が複数存在する場合は、\(t\) が \(cnt_t<0\) を満たす最小の \(t\) であることから、\(B_i\) の値は関係なく、\(A_i\) が最も大きい人を選べばよいです。

優先度付きキューなどを使うと計算量は \(O(NlogN)\) です。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N; cin >> N;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq1;
    priority_queue<int> pq2;
    map<int,int> mp;
    int ans=N;
    for(int i=0;i<N;i++){
        int A,B; cin >> A >> B;
        if(A<B){
            mp[A]--; mp[B]++;
            ans--;
        }
        else pq1.emplace(B,A);
    }
    int cnt=0;
    for(auto x:mp){
        while(!pq1.empty()&&pq1.top().first<=x.first){
            pq2.push(pq1.top().second); pq1.pop();
        }
        cnt+=x.second;
        while(cnt<0){
            if(pq2.empty()||pq2.top()<=x.first){
                cout << -1 << endl; return 0;
            }
            cnt++; ans--;
            mp[pq2.top()]--; pq2.pop();
        }
    }
    cout << ans << endl;
}