We call the two conditions in the problem condition \(1\) and condition \(2\). If \(G\) is not a DAG (Directed Acyclic Graph), then obviously no \(P\) satisfies condition \(1\), so we assume that \(G\) is a DAG.

In order for \(P\) to satisfy the two conditions, it is necessary that \(P_s \leq R_s\) and \(P_s \leq P_t-1 \leq R_t-1\) for all edges \((s, t)\). Thus, for edge \((s, t)\), replacing \(R_s \leftarrow \min\{R_s, R_t-1\}\) does not change the answer to the problem. In the reverse order of an arbitrary topological order of \(G\), repeatedly perform the replacement above, so as to fulfill \(R_s \lt R_t\) for all edges \((s, t)\). Hereinafter, we assume that \(R_s \lt R_t\) for all edges \((s, t)\).

Consider constructing the permutation \(P\) by successively assigning integers \(1, 2, \ldots, N\) as \(P_v\) for a chosen vertex \(v\). In the process, consider the situation where integers \(1, 2, \ldots, i-1\) are already assigned to vertices, and we now need to decide the vertex to assign integer \(i\). In order that the resulting \(P\) satisfies the conditions \(1\) and \(2\), it is necessary that

• \(L_v \leq i\) (by condition \(2\)) and
• for all edge \((u, v)\) going into \(v\), an integer is already assigned to \(u\) (by condition \(1\)).

Let us call such a vertex an assignable vertex. In fact, in order to construct \(P\) satisfying conditions \(1\) and \(2\), it is optimal to assign integer \(i\) to the assignable vertex \(v\) with minimum \(R_v\) (proved later).

Therefore, in order to solve this problem, it is sufficient to greedily try:

• assigning integer \(i\) to the assignable vertex \(v\) with minimum \(R_v\) for \(i = 1, 2, \ldots, N\) in this order;

and check if the resulting \(P\) actually satisfies conditions \(1\) and \(2\). By using a priority queue to obtain “the assignable vertex \(v\) with minimum \(R_v\),” this problem can be solved in a total of \(O(N\log N)\) time.

Proof of optimality

Let \(P\) be a permutation satisfying conditions \(1\) and \(2\). By rearranging the indices of the vertices, we can assume that \(P = (1, 2, \ldots, N)\) (by letting the vertex that integer \(i\) was assigned be vertex \(i\)).

In the process of constructing this \(P\), when assigning integer \(x\), suppose that, although “the assignable vertex \(v\) with minimum \(R_v\)” was vertex \(y\), integer \(x\) was assigned to vertex \(x\), where \(R_x \gt R_y\). In other words, suppose that there is an integer pair \((x, y)\) satisfying \(1 \leq x \lt y \leq N\) such that:

• there is no edge from vertices \(x, x+1, \ldots\) and \(N\) to vertex \(y\);
• \(L_y \leq x\); and
• \(R_x \gt R_y\).

We show that, even if we assign integer \(x\) to vertex \(y\) instead of vertex \(x\), the resulting permutation

\[P' = (P'_1, P'_2, \ldots, P'_{N-1}, P'_N) \coloneqq (1, 2, \ldots, x-1, x+1, x+2, \ldots, y, x, y+1, \ldots, N)\]

also satisfies conditions \(1\) and \(2\).

First, \(P'\) satisfies condition \(1\) because \(P\) satisfies condition \(1\) and “there is no edge from vertices \(x, x+1, \ldots\) and \(N\) to vertex \(y\).”

Next, \(L_i \leq P'_i\) for all \(i\) because, for the unique vertex \(y\) where the assigned integer decreased from \(P\) to \(P'\), it still holds that \(L_y \leq x = P'_y\).

Finally, we show that \(P'_i \leq R_i\) for all \(i\). It is sufficient to show that for all vertices \(x, x+1, \ldots, y-1\), in which the assigned integers increased from \(P\) to \(P'\). As described below, we can see that \(R_y \leq R_z\) for all such vertices \(z\):

• If \(z\) is assignable, then \(R_y \leq R_z\), because \(y\) is “the assignable vertex \(v\) with minimum \(R_v\).”
• If \(z\) is not assignable, then there is a path from an assignable vertex \(w\) to vertex \(z\); then, by the assumption that \(R_u \lt R_v\) for all edge \((u, v)\), we have \(R_ y \leq R_w \lt R_z \).

Hence, \(P'_z = z+1 \leq y \leq R_y \leq R_z\).