Temporal alignment of two time series
OK.  So the problem is as follows (with different notation):

Inputs: disjoint intervals $I_1,\dots,I_k$; disjoint intervals $J_1,\dots,J_m$
Output: disjoint intervals $K_1,\dots,K_n$ that are a "refinement" of the $I,J$-intervals

The $I$-intervals are not necessarily disjoint from the $J$-intervals.  We want the $K$-intervals to have the following property: if $x,y$ are in the same $K$-interval, then $x,y$ are in the same $I$-interval and $x,y$ are in the same $J$-interval.

This can be solved.  Basically, you use a 'merge' procedure vaguely akin go the merge operation from Mergesort, but adjusted to deal with intervals.    I'll assume the $I$-intervals are in sorted order, and the $J$-intervals are in sorted order (so $I_1$ is the leftmost/smallest interval of the $I$-intervals, etc.).

The algorithm considers how $I_1$ compares to $J_1$:


If $I_1$ is wholly to the left of $J_1$ (they don't overlap, and $I_1$ is smaller than $J_1$), then we output $I_1$, delete $I_1$ from the $I$-list, and continue.
If $I_1$ is wholly to the right of $J_1$ (they don't overlap, and $I_1$ is larger than $J_1$), then we output $J_1$, delete $J_1$ from the $J$-list, and continue.
If $I_1,J_1$ overlap and $I_1$ is contained in $J_1$, then do the following: if $I_1$ is the interval $[a,b]$ and $J_1$ is the interval $[c,d]$ (so $c&lt;a&lt;b&lt;d$), output the interval $[c,a]$, output the interval $[a,b]$, delete $I_1$ from the $I$-list, delete $J_1$ from the $J$-list, and insert $[b,d]$ to the front of the $J$-list.
If $I_1,J_1$ overlap and $J_1$ is contained in $I_1$, do the symmetrical equivalent of the previous case.
If $I_1,J_1$ overlap but neither is wholly contained in the other, and the left endpoint of $I_1$ is to the left of the left endpoint of $J_1$, do the following: if $I_1$ is the interval $[a,b]$ and $J_1$ is the interval $[c,d]$ (so that $a&lt;c&lt;b&lt;d$), output the interval $[a,c]$, output the interval $[c,b]$, delete $I_1$ from the $I$-list, delete $J_1$ from the $J$-list, and insert $[b,d]$ to the front of the $J$-list.
If $I_1,J_1$ overlap but neither is wholly contained in the other, and the left endpoint of $J_1$ is to the left of the left endpoint of $I_1$,  do the symmetrical equivalent of the previous case.


As you can see, once you've sorted the intervals, this can be handled by a linear scan using a case analysis.  The total number of intervals in the output will be at most twice the total number of intervals in the input (i.e., $n \le 2(k+m)$).