Let’s consider the contribution of a pair of people \(i\) and \(j\) to the total dissatisfaction.

We analyze by cases based on the relationship between intervals \([L_i,R_i]\) and \([L_j,R_j]\).

[1] When there is no common part

This is the case where \(L_i < R_i < L_j< R_j\) or \(L_j< R_j < L_i< R_i\).

Since the times when the two people are in the movie theater do not overlap, the contribution is \(0\).

[2] When they intersect

This is the case where \(L_i < L_j< R_i< R_j\) or \(L_j< L_i < R_j< R_i\).

No matter how people \(i,j\) are seated, exactly one of people \(i,j\) will cross in front of where the other is sitting exactly once. Therefore, the contribution is \(1\).

[3] When one contains the other

This is the case where \(L_i < L_j < R_j < R_i\) or \(L_j < L_i < R_i < R_j\).

By symmetry, let’s assume \(L_i < L_j < R_j < R_i\). In this case, if \(P_i > P_j\) then the contribution is \(0\), and if \(P_i < P_j\) then the contribution is \(2\).

From the above, we can see that to minimize the sum of contributions (= total dissatisfaction), we need to minimize the number of pairs \((i,j)\) that satisfy both \(L_i < L_j < R_j < R_i\) and \(P_j > P_i\).

Here, if we create a graph where we draw a directed edge from vertex \(i\) to vertex \(j\) for pairs \((i,j)\) satisfying \(L_i < L_j < R_j < R_i\), this graph becomes a DAG (a graph with no cycles). Therefore, there exists a permutation \(P\) of \((1,2,\ldots,N)\) such that if \(L_i < L_j < R_j < R_i\), then \(P_j < P_i\). Thus, we need to find the lexicographically smallest permutation \(P\) of \((1,2,\ldots,N)\) that satisfies \(P_j < P_i\) whenever \(L_i < L_j < R_j < R_i\).

This can be found using the following greedy algorithm:

• For \(k=N,N-1,\ldots,1\), perform the following operation:
  • Take the largest \(i\) that satisfies the following conditions:
    • Person \(i\)’s seat has not been determined yet.
    • There does not exist a person \(j\) such that \(L_j < L_i < R_i < R_j\) and whose seat has not been determined yet.
  • Set \(P_i=k\).

Intuitively, this is a greedy algorithm that seats people in order of decreasing seat number, choosing the person with the largest number among those who can be seated.

By implementing the above appropriately, we can solve this problem correctly. The time complexity is \(O(N^3)\) per test case.

Sample Implementation (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)