人 \(i\) と人 \(j\) の二人組が不満度の総和に与える貢献度について考えます。

区間 \([L_i,R_i]\) と \([L_j,R_j]\) の関係で場合分けします。

[1] 共通部分がないとき

\(L_i < R_i < L_j< R_j\) または \(L_j< R_j < L_i< R_i\) となるような場合です。

\(2\) 人が映画館にいる時間は被っていないので、貢献度は \(0\) です。

[2] 交差しているとき

\(L_i < L_j< R_i< R_j\) または \(L_j< L_i < R_j< R_i\) となるような場合です。

人 \(i,j\) がどのように座ってもちょうど \(1\) 回人 \(i,j\) の一方が座っている前をもう一方が横切ります。したがって、貢献度は \(1\) です。

[3] 包含しているとき

\(L_i < L_j < R_j < R_i\) または \(L_j < L_i < R_i < R_j\) となるような場合です。

対称性より \(L_i < L_j < R_j < R_i\) とします。このとき、 \(P_i > P_j\) なら貢献度は \(0\) 、 \(P_i < P_j\) なら貢献度は \(2\) となります。

以上より、貢献度の総和（=不満度の総和）を最小化するためには \(L_i < L_j < R_j < R_i\) と \(P_j < P_i\) を共に満たす \((i,j)\) の組を最大化すれば良いことが分かります。

ここで、\(L_i < L_j < R_j < R_i\) を満たす \((i,j)\) に対して頂点 \(i\) から頂点 \(j\) に有向辺を張ったようなグラフは DAG （閉路を含まないグラフ）になるので、\(L_i < L_j < R_j < R_i\) ならば \(P_j < P_i\) を満たすような \((1,2,\ldots,N)\) の順列 \(P\) が存在します。したがって、\(L_i < L_j < R_j < R_i\) ならば \(P_j < P_i\) を満たす \((1,2,\ldots,N)\) の順列 \(P\) のうち辞書順最小のものを求めれば良いです。

そして、これは以下のような貪欲法で求めることができます：

• \(k=N,N-1,\ldots,1\) に対して以下の操作を行う。
  • 以下の条件を満たす最大の \(i\) を取る。
    • 人 \(i\) の席はまだ確定していない。
    • \(L_j < L_i < R_i < R_j\) かつ席がまだ確定していないような人 \(j\) が存在しない。
  • \(P_i=k\) とする。

直感的には席の番号が大きい順に座れる人のうち最も番号が大きい人を順に座らせていく貪欲法です。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(N^3)\) です。

実装例(Python3)

for _ in range(int(input())):
    n = int(input())
    l = [0] * n
    r = [0] * n
    for i in range(n):
        l[i], r[i] = map(int, input().split())
    ans = [-1] * n
    for p in reversed(range(n)):
        for i in reversed(range(n)):
            if ans[i] != -1:
                continue
            ok = True
            for j in range(n):
                ok &= ans[j] != -1 or not l[j] < l[i] < r[i] < r[j]
            if not ok:
                continue
            ans[i] = p + 1
            break
    print(*ans)