Tangled Wires

View every wire $i$ as the interval between its two current endpoints.

Reachable arrangements

We use the following lemma.

Initially, wire $i$ connects $[a_i,b_i]$. Let $C$ be a sequence of length $2N$ in which every wire number occurs exactly twice. The sequence $C$ is reachable if and only if both occurrences of every $i$ lie inside $[a_i,b_i]$.

During one operation, each new endpoint lies between the two previous endpoints of the same wire. Therefore every reachable arrangement satisfies the condition.

The converse is the standard uncrossing lemma. Overlay the current matching and the target matching, pairing edges with the same label. Their union decomposes into even alternating cycles. If the two matchings differ, one alternating cycle contains two crossing current edges whose crossing can be resolved in the required direction while every target edge remains inside the new interval of the same label. This operation strictly decreases the sum of current interval lengths. Repeating this argument and applying induction on that sum reaches the target matching.

The problem is therefore equivalent to the following scheduling problem.

• Wire $i$ gives two identical jobs with label $i$.
• Each job must be scheduled at a position from $a_i$ through $b_i$.
• Exactly one job is scheduled at every position.
• The resulting label sequence must be lexicographically minimum.

Which label can be chosen now?

Construct the answer from left to right, and suppose the current position is $p$. Let $r_i\in\{0,1,2\}$ be the number of unscheduled jobs of wire $i$.

For every $d\geq p$, define the slack

$$S(d)=d-p+1-\sum_{b_i\leq d}r_i.$$

Every remaining job whose deadline is at most $d$ must fit into positions $p,p+1,\cdots,d$, so every feasible state satisfies $S(d)\geq0$.

Suppose that one job of wire $i$ is scheduled at position $p$, after which the current position becomes $p+1$. The slack changes as follows.

• If $d<b_i$, then $S(d)$ decreases by $1$.
• If $d\geq b_i$, then $S(d)$ does not change.

Let $z$ be the smallest index at least $p$ with $S(z)=0$. Since the number of remaining jobs equals the number of remaining positions, $S(2N)=0$, so $z$ always exists.

Wire $i$ can be scheduled at the current position while preserving feasibility if and only if both conditions below hold.

• $a_i\leq p$ and $r_i>0$.
• $b_i\leq z$.

Necessity of the second condition follows immediately from the slack update. Sufficiency follows from Hall's condition for matching unit jobs to interval positions. After deleting the current position, the only Hall constraints that can become tighter are intervals beginning at the current position, and those constraints are exactly the slack inequalities above.

Thus, at every position, choose the smallest wire number satisfying these conditions. This gives the lexicographically smallest feasible sequence.

Data structures

Use two segment trees.

The first tree stores all values $S(d)$. It supports range addition and finding the first zero at or after $p$. After choosing wire $i$, add $-1$ to $[p,b_i-1]$.

The second tree is indexed by deadlines $b_i$. If $a_i\leq p$ and $r_i>0$, store value $i$ at index $b_i$; otherwise store infinity. The minimum on $[p,z]$ is the wire chosen now. After using a wire twice, replace its value by infinity.

A constant number of segment-tree operations is performed for each position. The time complexity is $O(N\log N)$ and the space complexity is $O(N)$.

Solution written by GPT5.6