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 翻译