wire intersection puzzle Given a rural area is only accessible via railroad. As part of a class on economic development, you've come up with a plan for electrifying these remote settlements. Your plan basically describes n wires connecting some stations along the railroad. ith wire goes between stations l[i] and r[i].
As we all know, wires can't cross because this leads to a short circuit, but they can have the same endpoints. Also, the wires cannot cross the railroad - so in other words, a wire should go either to the left or the right of the railroad.
Is it possible to place the wires in such a way that they don't intersect?
Example
For l = [1, 2, 3] and r = [4, 6, 5], it is possible to arrange the wires such that they do not intesect , so the answer is True

For l = [1, 2, 3] and r = [4, 5, 6], it is not possible to arrange, so the answer is False

For l=[1,3,2,4] and r=[4,5,5,6] the answer is True
What I need is a way to solve the puzzle and how to do it. It seems almost similar to the travelling sales man problem, but I can be wrong too. So how to solve it? How to understand if the arrangements are possible or not?
 A: *

*For every connection, create a set consisting of all the nodes between two connected nodes. In your first example, these sets would be $\{2,3\};\{3,4,5\}; \text{and} \{4\}$.

*Any intersection between two sets such that one is not a subset of another can only be connected by a subset of one of the two sets because an intersection means that there is at least one connection on both sides of the intersection. A subset, however, does not interfere with this as they can go between one of the wires and the railroad. There is an intersection at $3$ in your first example. There is a subset of $4$ between the other two sets. There is no intersection between the first and last sets. Your first example is therefore true because the intersection is covered by the $3$ to $5$ connection, which has the subset of $4$.


In short, if any set intersects two different non-subsets, it fails.
Here's a better written algorithm:


*

*For each wire, generate a set consisting of the nodes between them.

*For each set, check if it intersects another set.

*If a set intersects another set, check if one is a subset of the other.


*

*If one is a subset of the other, no conflict, move on.

*If not, search for another set containing the intersection.


*

*If there is not another subset containing the intersection, move on.

*If there is another set containing the intersection, check if it is a subset of either of the two sets.


*

*If it is a subset, no conflict, move on.

*If it is not a subset, there is a conflict, and this wiring does not work.




*If you reach the end of all the comparisons without any of the sets conflicting, this wiring works.


There are a few ways you can improve this, including not storing an entire set, just the end points, sorting the sets by their left endpoints, etc.
