[1] Checking if the answer is \(-1\)

Let us first consider how to check if the objective is achievable at all by performing any number of swaps. Since it is optimal to assign a higher score to a person with a greater \(B_i\) (stricter requirement), the objective is achievable if and only if:

\(B_i \leq A_i\) for every \(i\) when \(A\) and \(B\) are sorted in ascending order.

This is probably the common first try, but we need to rephrase this condition a little.

For \(1 \leq t \leq 10^9\),

let \(cnt_t=(\) the number of \(i\) such that \(B_i\leq t\) \()-(\) the number of \(i\) such that \(A_i\leq t\) \()\).

Then, \(cnt_t \geq 0\) holds for every \(t\).

These two conditions are equivalent.

[2] Finding the maximum number of unswapped people

If \(B_i \leq A_i\) holds for every \(i\) already in the beginning, the answer is \(N\).

Otherwise, we have to find a set \(S\) of people whose scores are swapped that minimizes \(|S|\). \(S\) must contain all people with \(A_i<B_i\) in the beginning.

So, let us initialize \(S\) as the set of people with \(A_i<B_i\) in the beginning, and add other people to \(S\) one at a time until \(cnt_t \geq 0\) holds for every \(t\).

In what order should we add people?

Consider the minimum \(t\) such that \(cnt_t < 0\) at the moment. Then, we must add Person \(i\) such that \(B_i \leq t\) and \(t < A_i\). If there is no such person, the objective is unachievable. If there are multiple such people, the person \(i\) with the maximum \(A_i\) should be chosen, because \(B_i\) does not matter since we have chosen the minimum \(t\) such that \(cnt_t<0\).

This solution works in \(O(NlogN)\) time by using, say, a priority queue.

Sample implementation (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;
}