[CF1462F] The Treasure of The Segments

[CF1462F] The Treasure of The Segments - 二分

Description

有n个区间，最少需要删除多少个区间才能使存在一条线段能够和其他所有线段均有交点

Solution

枚举这条线段是谁，那么问题转化成如何快速求与某一条线段相交的线段条数

如果 ([l,r], [l',r']) 不相交，那么 (l>r', l'>r) 必然满足其一，且不会同时满足

因此我们将所有线段的左端点排个序，右端点排个序，分别二分即可

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

#define int long long

void solve()
{
    int n;
    cin >> n;

    vector<pair<int, int>> seg(n + 2);
    vector<int> pl(n), pr(n);
    for (int i = 1; i <= n; i++)
    {
        int l, r;
        cin >> l >> r;
        seg[i] = {l, r};
        pl[i - 1] = l;
        pr[i - 1] = r;
    }

    sort(pl.begin(), pl.end());
    sort(pr.begin(), pr.end());

    int ans = 1e18;
    for (int i = 1; i <= n; i++)
    {
        auto [l, r] = seg[i];
        int t1 = lower_bound(pr.begin(), pr.end(), l) - pr.begin();
        int t2 = pl.end() - upper_bound(pl.begin(), pl.end(), r);
        ans = min(ans, t1 + t2);
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}