Two Professors

#include<bits/stdc++.h>
#define fastio  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define print(v) for(auto it : v) cout << it << ' '; cout << endl;
#define valid(i, j, n, m) (i >= 1 && i <= n && j >= 1 && j <= m)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << #x << "--> " << x << endl;
#define int long long
#define pii pair<int, int>
#define ppii pair<pii, int>
#define fi first
#define se second
#define inf 1e18
using namespace std;

const int mod = 1e6 + 7;
const int N = 2e5 + 5;

struct Interval
{
    int tval, type, id;
    Interval(int _tval, int _type, int _id)
    {
        tval = _tval;
        type = _type;
        id = _id;
    }
    bool operator<(Interval const & A) const
    {
        if (tval != A.tval) return tval < A.tval;
        else  return type > A.type;
    }
};
main()
{
#ifndef ONLINE_JUDGE
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
#endif
    int tc; cin >> tc;
    while (tc--)
    {
        int n; cin >> n;
        vector<Interval>vec;
        for (int i = 1; i <= n; i++)
        {
            int st; cin >> st;
            int ed; cin >> ed;
            vec.push_back(Interval(st, 1, i));
            vec.push_back(Interval(ed, 2, i));
        }

        if (vec[0].tval > vec[2].tval)
        {
            vec[0].id = 2, vec[2].id = 1;
            vec[1].id = 2, vec[3].id = 1;
        }

        sort(vec.begin(), vec.end());
        deque<int>available;
        int rooms[n + 1], rnum = 0;
        for (int i = 0; i < vec.size(); i++)
        {
            int type = vec[i].type;
            int id = vec[i].id;

            if (type == 1)
            {
                if (available.empty() == false)
                {
                    if (id == 2)
                    {
                        if (available.size() == 1) // only one free rooms are there
                        {
                            int freeRoom = available.front();
                            if (rooms[1] == freeRoom)
                            {
                                ++rnum;
                                rooms[2] = rnum;
                            }
                            else
                            {
                                rooms[2] = freeRoom;
                                available.pop_front();
                            }
                            continue;
                        }

                        // more than 1 free rooms
                        int freeRoom1 = available.front();
                        int freeRoom2 = available.back();

                        if (rooms[1] == freeRoom1) // if freeRoom1 is the room where meeting 1 held
                        {
                            rooms[2] = freeRoom2; // host it in the second free room
                            available.pop_back();
                        }
                        else // else you can safely held meeting 2 in freeRoom1
                        {
                            rooms[2] = freeRoom1;
                            available.pop_front();
                        }
                    }
                    else
                    {
                        rooms[id] = available.front();
                        available.pop_front();
                    }
                }
                else
                {
                    // if no free rooms are there you have no other option without allocating a new room
                    rnum++;
                    rooms[id] = rnum;
                }
            }
            else
            {
                int Allocated_Room = rooms[id];
                available.push_back(Allocated_Room);
            }
        }
        cout << rnum << endl;
        // for (int i = 1; i <= n; i++) cout << rooms[i] << ' ';
        // cout << endl;
    }
}