View every wire as the interval between its two current endpoints.
Reachable arrangements
We use the following lemma.
Initially, wire connects . Let be a sequence of length in which every wire number occurs exactly twice. The sequence is reachable if and only if both occurrences of every lie inside .
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.
Which label can be chosen now?
Construct the answer from left to right, and suppose the current position is . Let be the number of unscheduled jobs of wire .
For every , define the slack
Every remaining job whose deadline is at most must fit into positions , so every feasible state satisfies .
Suppose that one job of wire is scheduled at position , after which the current position becomes . The slack changes as follows.
Let be the smallest index at least with . Since the number of remaining jobs equals the number of remaining positions, , so always exists.
Wire can be scheduled at the current position while preserving feasibility if and only if both conditions below hold.
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 . It supports range addition and finding the first zero at or after . After choosing wire , add to .
The second tree is indexed by deadlines . If and , store value at index ; otherwise store infinity. The minimum on 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 and the space complexity is .
Solution written by GPT5.6
