Legendary Magician

• Time : $O(nlogn)$
• Space : $O(n)$

#include<bits/stdc++.h>
using namespace std;

int solve (int n, vector<int> A, vector<int> B) {
    vector<pair<int,int>> S;
    for(int i = 0; i < n; i++) S.push_back({A[i],B[i]});
    sort(begin(S), end(S));
    int res = 0, ma = 0;
    for(int i = 0; i < n; i++) {
        auto [s,e] = S[i];
        if(s > ma) {
            res += 1;
            ma = e;
        } else ma = min(ma,e);
    }
    return res;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i = 0; t_i < T; t_i++)
    {
        int n;
        cin >> n;
        vector<int> A(n);
        for(int i_A = 0; i_A < n; i_A++)
        {
            cin >> A[i_A];
        }
        vector<int> B(n);
        for(int i_B = 0; i_B < n; i_B++)
        {
            cin >> B[i_B];
        }

        int out_;
        out_ = solve(n, A, B);
        cout << out_;
        cout << "\n";
    }
}