题目传送门

题目大意

给出个的区间，有交叉的区间可以合并为同一个，从中删去一个，最多可以形成多少个独立的区间

思路

若是没有删去一个的条件，对于所有的区间可以先对升序排序，然后用栈进行合并
1.插入一个新的区间，若栈顶的区间的，将栈顶区间退栈，退栈的区间与待插入的区间可以合并为新的待插入区间
2.重复1操作，直到栈空或者栈顶元素无法合并
3.将待插入区间入栈
4.栈的大小即为最终独立的区间的个数
不难发现对于一个区间来说，只要满足的区间都能被它合并
因此我们可以枚举删去每一个单独区间的情况
当删去某一个区间(假设要删去排序后的第个区间)，其后的区间最多能够合并到已经合并在栈里的区间取决于其后区间的最小值
所以维护的后缀最小值(将x位置的后缀最小值记作)，二分能够合并的最小位置
对于不删去第个区间的情况，则是二分能够合并的最小位置，两个位置之差就是删去第个区间与最终合并答案的差
需要注意当枚举最后一个区间时的边界情况
以及若时代表第i个区间无法被后面合并，则差值

AC代码

// #pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 2e5 + 10;
pii stk[maxn];
pii seg[maxn];
int suf[maxn];
int ans[maxn];
int cal(int n)
{
    int top = 0;
    suf[n - 1] = seg[n - 1].second;
    for (int i = n - 2; i >= 0; --i)
    {
        suf[i] = min(suf[i + 1], seg[i].second);
    }
    for (int i = 0; i < n; ++i)
    {
        int l = 1, r = top;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (stk[mid].first >= suf[i + 1])
                r = mid - 1;
            else
                l = mid + 1;
        }
        ans[i] = l;
        if (i == n - 1)
            ans[i] = top;
        l = 1, r = top;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (stk[mid].first >= suf[i])
                r = mid - 1;
            else
                l = mid + 1;
        }
        ans[i] -= l;
        if (i < n - 1 && suf[i + 1] > seg[i].first)
            --ans[i];
        if (top >= 1 && seg[i].second <= stk[top].first)
        {
            stk[top].first = seg[i].first;
            stk[top].second = min(stk[top].second, seg[i].second);
            while (top >= 2 && stk[top - 1].first >= stk[top].second)
            {
                stk[top - 1].first = stk[top].first;
                stk[top - 1].second = min(stk[top - 1].second, stk[top].second);
                --top;
            }
        }
        else
        {
            stk[++top] = seg[i];
        }
    }
    int res = 0;
    for (int i = 1; i < n; ++i)
    {
        res = max(res, top + ans[i]);
    }
    return res;
}

int main()
{
    int t;
    read(t);
    for (int i = 1; i <= t; ++i)
    {
        int n;
        read(n);
        for (int i = 0; i < n; ++i)
        {
            read(seg[i].second), read(seg[i].first);
        }
        sort(seg, seg + n);
        printf("%d\n", cal(n));
    }
}