题解

思路

考虑两个人 $i,j$ 对总不满度的贡献。

做法

两区间不相交时贡献为 $0$；交叉但不包含时，无论如何安排座位，贡献都为 $1$。若 $L_i<L_j<R_j<R_i$，当 $P_j<P_i$ 时这对的可变贡献为 $0$，否则为 $2$。因此对每个严格包含关系，内层区间应获得更小的座位号。从外层人向内层人连有向边，得到一个 DAG，满足所有边的排列一定能把可变贡献全部降为零。

从座位号 $N$ 到 $1$ 倒序分配。当前可选的人是 DAG 中入度为零的顶点，即尚未安排的区间中没有其他区间严格包含它。为使最终的 $P$ 字典序最小，最大座位号应优先给人员编号最大的可选顶点，用大根堆执行拓扑排序即可。

复杂度

建图需要 $O(N^2)$ 时间与空间，堆操作需要 $O(N\log N)$ 时间。