# Matching elements of two sequences: choosing the best one

I have the following problem.

Let $P$ and $Q$ be two ordered sequences of time instants. $[p_0,p_1,\ldots,p_n]$ and $[q_0,q_1,\ldots,q_m]$ are the elements of $P$ and $Q$ respectively. A first constraint on the elements of those sequences is $p_i \in \mathcal{R}$ and $p_i < p_{i+1}$ (the same applies for $q_i$)

From $P$ and $Q$ a sequence $R$ can be obtained. $R$ is a sequence of sets of elements of $P$ and $Q$: $[r_0,r_1,\ldots,r_n]$. As $P$ and $Q$ are sequence of time instants, $R$ is a sequence of time intervals.

There are a few constraints on the sets $r_i$:

• They must contain elements of both $P$ and $Q$
• They must contain at most one element of $P$ or at most one element of $Q$. For example, $(p_0,p_1,q_0)$ is valid, but $(p_0,q_0,q_1,p_1)$ is not
• Sets must not overlap: if $p_0 \in r_i$ then $p_1 \in {r_i,r_{i+1}}$ (the same for Q), and $max(r_i) < min (r_{i+1})$.

I'm stuck on this point: the output sets $r_i$ should be as precise as possible, meaning that the interval as to be the as tight as possible. So I have to define a metric that can be used to select the best sequence $R$ among all the achievable from two sequences $P$ and $Q$. The precision of a set $t(r_i)$ is defined as $max(r_i)-min(r_i)$

For example:let $P$ be $[0,2,6]$ and $Q$ be $[1,5,7]$. According to the aforementioned rules, two possible sequences $R$ are possible:

• $R_0=[(0,1,2),(5,6,7)]$
• $R_1=[(0,1),(2,5),(6,7)]$

What metric should be used to select the best between $R_0$ and $R_1$? $R_0$ minimizes $\sum_i t(r_i)$ and seems to have better properties compared to $R_1$ (it correctly states that in both $P$ and $Q$ there aren't time instants between 2 and 5. However, $R_1$ has a lower mean value (1.67 vs 2).

• You cannot ask for the best metric if you do not give us the context. How can you say that "$R_0$ seems to have better properties"? – André Souza Lemos Jun 1 '15 at 17:04