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:

Segment $I_i$ is entirely to the right of segment $I_j$.
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?
Construct a graph in which each vertex corresponds to an endpoint of an interval. Then add the following edges:


If $\ell_i,r_i$ are the endpoints of $I_i$, then add the edge $\ell_i \to r_i$.
For a constraint $I_i &lt; I_j$, add the edge $r_i \to \ell_j$.
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.)