题解

思路

先检查所有已知楼层是否互不相同，以及同一人的已知上下楼层是否满足 $A_i<B_i$。

做法

公平条件等价于把 $1,2,\ldots,2N$ 划分为若干连续偶数长度区间：若某段长度为 $2k$，它的前 $k$ 个位置全部是上电梯事件，后 $k$ 个位置全部是下电梯事件，并且第 $t$ 个上车者恰在向后偏移 $k$ 的位置下车。于是可以枚举区间 $[l,r]$，逐对检查其中已知事件的类型、人员编号和另一端点是否相容。

令 $dp_i$ 表示前 $i$ 个楼层能否被合法区间完整划分，初始 $dp_0=\mathrm{true}$；从每个可达位置枚举下一段，若该段相容就转移到它的右端点。某个合法补全必然产生这样的分段，反之每个通过检查的分段都能把尚未确定的成对位置分配给同一人，因此该 DP 充要。

复杂度

时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。