CF1841D Pairs of Segments

当且仅当存在至少一个 $x$ 满足 $l_1 \le x \le r_1$ 且 $l_2 \le x \le r_2$ 时，两个区间 $[l_1, r_1]$ 和 $[l_2, r_2]$ 相交。 一个区间数组 $[[l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]]$ 被称为“美丽的”，当且仅当 $k$ 是偶数，并且可以将该数组中的元素分成 $\frac{k}{2}$ 对，使得： - 每个元素恰好属于一对； - 每对中的两个区间相交； - 不同对中的区间互不相交。 例如，数组 $[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$ 是美丽的，因为可以如下分成 $3$ 对： - 第一个元素（区间 $[2, 4]$）和第三个元素（区间 $[2, 4]$）； - 第二个元素（区间 $[9, 12]$）和第五个元素（区间 $[10, 13]$）； - 第四个元素（区间 $[7, 7]$）和第六个元素（区间 $[6, 8]$）。 可以看到，每对中的区间相交，不同对中的区间互不相交。 现在给定一个包含 $n$ 个区间的数组 $[[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]]$。你需要删除尽可能少的元素，使得剩下的数组是美丽的。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2000$），表示区间的数量。接下来有 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \le r_i \le 10^9$），表示第 $i$ 个区间。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $2000$。

对于每个测试用例，输出一个整数，表示你需要删除的最少元素个数，使得剩下的数组是美丽的。

在样例的第一个测试用例中，只需删除第 $5$ 个区间即可。此时得到的数组 $[[2, 4], [9, 12], [2, 4], [7, 7], [10, 13], [6, 8]]$ 是美丽的。 在样例的第二个测试用例中，可以删除第 $1$、$3$ 和 $4$ 个区间。此时得到的数组 $[[2, 8], [5, 6]]$ 是美丽的。 在样例的第三个测试用例中，需要删除整个数组。 由 ChatGPT 4.1 翻译