# Existence of interval arrangement satisfying constraints

Problem statement:

Input:

(a) A natural number $$n$$.

(b) $$m$$ requirements on $$I_1,\ldots,I_n$$ of the form:

1. Segment $$I_i$$ is entirely to the right of segment $$I_j$$.
2. Segments $$I_i$$ and $$I_j$$ intersect.

Output:

Is it possible to find $$n$$ non-empty segments (on the real number line) which fulfill the $$m$$ requirements?

Here is my solution attempt.

I started by considering what happens when I have only requirements of type 1 (no particular reason, just easier to visualize). I created a directed graph with $$V=\{v_1,v_2,\ldots,v_n\}$$ nodes, where each node represents a segment. I added an edge $$e=(u,v)$$ iff the segment $$u$$ is to the right of segment $$v$$ ($$e$$ represents a requirement of type 1). A solution exists if the graph is a DAG, which can be checked in linear time using DFS.

My problem is with edges of type 2. I understand that a solution exists iff there is no edge of type 2 between two nodes which have a path with edges of type 1 between them. I believe I found an $$O((m+n)m)=O(mn+m^2)$$ algorithm using BFS from every node $$u$$ for which an $$e=(u,v)$$ of type 2 exists. I run the BFS from the node $$u$$ and check if $$v$$ is discovered. If it is, no solution exists.

Is there a linear time algorithm for this?

1. If $\ell_i,r_i$ are the endpoints of $I_i$, then add the edge $\ell_i \to r_i$.
2. For a constraint $I_i < I_j$, add the edge $r_i \to \ell_j$.
3. For a constraint $I_i \cap I_j \neq \emptyset$, add the edges $\ell_i \to r_j$ and $\ell_j \to r_i$.