5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.