提出 #66808142

---

ソースコード 拡げる

from heapq import *


def solve():
    n = int(input())
    L = [0] * n
    R = [0] * n
    for i in range(n):
        L[i], R[i] = map(int, input().split())

    to = [[False] * n for _ in range(n)]
    for i in range(n):
        li, ri = L[i], R[i]
        for j in range(i + 1, n):
            lj, rj = L[j], R[j]
            if li < lj < rj < ri:
                to[i][j] = True
            elif lj < li < ri < rj:
                to[j][i] = True

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if to[i][k] and to[k][j]:
                    to[i][j] = True

    P = [0] * n
    ma = [n - 1] * n
    used = [False] * n
    for i in range(n):
        cc = 0
        for j in range(i + 1, n):
            if to[i][j]:
                cc += 1

        for k in range(n):
            if used[k]:
                continue
            cnt = [0] * n
            for j in range(i + 1, n):
                if to[i][j]:
                    cnt[min(k, ma[j])] += 1
                else:
                    cnt[ma[j]] += 1

            ok = True
            p = 0
            for j in range(n):
                if j > 0:
                    cnt[j] += cnt[j - 1]
                if used[j] or j == k:
                    cnt[j] += 1
                p += 1
                if cnt[j] > p:
                    ok = False
                    break

            if ok:
                P[i] = k + 1
                used[k] = True
                for j in range(n):
                    if to[i][j]:
                        ma[j] = min(ma[j], k)
                break
    print(*P)


for _ in range(int(input())):
    solve()

提出情報

ジャッジ結果