AT_arc200_c [ARC200C] Movie Theater

给定正整数 $N$ 和长度为 $N$ 的正整数序列 $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$。这里保证 $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ 互不相同。 某电影院有 $N$ 个座位，左右排成一行。从左到右第 $i$ 个座位称为座位 $i$。 有 $N$ 个人（编号 $1$ 到 $N$）来到电影院。你需要为每个人分配一个座位。若将第 $i$ 个人分配到座位 $P_i$，则第 $i$ 个人会在时刻 $L_i$ 经过座位 $1,2,\ldots,P_i-1$ 并坐到座位 $P_i$，在时刻 $R_i$ 经过座位 $1,2,\ldots,P_i-1$ 离开座位。 第 $i$ 个人的**不满度**定义为在时刻 $L_i$ 到 $R_i$ 之间（不包括 $L_i,R_i$）被其他人经过座位 $P_i$ 的次数。 请你在所有使 $1,2,\ldots,N$ 的排列 $P$ 中，找到总不满度最小且字典序最小的 $P$。 有 $T$ 组测试数据，请分别输出答案。

输入按以下格式从标准输入读入。 > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组测试数据格式如下： > $N$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_N$ $R_N$

输出 $T$ 行。 第 $i$ 行输出第 $i$ 组测试数据中，使所有人的不满度总和最小且字典序最小的排列 $P$，用空格分隔。

### 数据范围 - $1\leq T\leq 500$ - $1\leq N\leq 500$ - $1\leq L_i < R_i \leq 2N$ - $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ 互不相同 - 所有测试数据中 $N$ 的总和不超过 $500$ - 输入的所有值均为整数 ### 样例解释 1 对于第 $1$ 组测试数据，若 $P=(2,1,3)$，过程如下： - 时刻 $1$：第 $1$ 个人坐到座位 $2$。 - 时刻 $2$：第 $2$ 个人坐到座位 $1$。 - 时刻 $3$：第 $2$ 个人离开座位 $1$。 - 时刻 $4$：第 $3$ 个人坐到座位 $3$，第 $1$ 个人的不满度增加 $1$。 - 时刻 $5$：第 $1$ 个人离开座位 $2$。 - 时刻 $6$：第 $3$ 个人离开座位 $3$。 此时总不满度为 $1$。无法使总不满度小于 $1$，且 $P=(2,1,3)$ 是所有总不满度为 $1$ 的排列中字典序最小的。因此答案为 $P=(2,1,3)$。 对于第 $2$ 组测试数据，无论如何分配，所有人的总不满度都是 $6$。 由 ChatGPT 4.1 翻译