CF1841D Pairs of Segments

这篇博客主要讲述了一个算法问题，题目是给定 $n$ 条线段，每对线段由两个相交的线段组成。要求删除最少的线段，使得剩余的线段可以分成若干对，且每对线段互不相交。文章通过贪心算法解决这个问题，具体实现代码也给出了。

题目大意

有 $n$ 条线段，一对线段由两个相交线段组成。

称某 $k$ 条线段为漂亮的线段组，如果 $k$ 条线段满足:

• $k$ 是偶数
• 可以分成 $k/2$ 对线段，且不同对线段中的线段各不相交

问最少删去多少条线段可以使这 $n$ 条线段是漂亮的。

思路

先 $O(n^2)$ 的处理出所有可能出现的线段对，每个线段对可以合成一条新的线段。在这些新线段中选取一些互不相交的线段，互不相交的线段数量即为漂亮线段组中线段数的一半。

问题即转化为经典的选择不相交区间问题：给出一堆区间，要求选择尽量多的区间，使得这些区间互不相交，求可选取的区间的最大数量。这里端点相同也算有重复。

贪心的解决这类问题，将这些线段右端点从小到大排序，每次选择与前面选择的线段不相交的线段。贪心正确性显然。

代码

struct sgm {
    int l, r;
};
bool cmp(sgm x, sgm y) {
    return x.r < y.r;
    //    return x.l > y.l;
}
bool is_pair(sgm x, sgm y) {
    return (x.l >= y.l && x.l <= y.r) || (x.r >= y.l && x.r <= y.r);
}
sgm a[2010], u[4000010];
int n, res, tot;
void solve() {
    tot = 0;
    cin >> n;
    rep(i, 0, n - 1) cin >> a[i].l >> a[i].r;
    rep(i, 0, n - 1) rep(j, i + 1, n - 1) {
        if (is_pair(a[i], a[j]) || is_pair(a[j], a[i]))
            u[tot++] = sgm{min(a[i].l, a[j].l), max(a[i].r, a[j].r)};
    }
    if (tot == 0) {
        cout << n << endl;
        return;
    }
    sort(u, u + tot, cmp);
    sgm tmp = u[0];
    res = 1;
    rep(i, 1, tot - 1) {
        if (!is_pair(tmp, u[i]) && !is_pair(u[i], tmp)) {
            res++;
            tmp = u[i];
        }
    }
    cout << n - 2 * res << endl;
}