Existence of interval arrangement satisfying constraints

Question

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?

Answer 1

Construct a graph in which each vertex corresponds to an endpoint of an interval. Then add the following edges:

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$.

Now check that there are no directed cycles. (This answer is inspired by an answer on stackexchange.)