Permute the subintervals of an interval partition to most closely align with a model partition
You can use integer linear programming (ILP) to solve this.  In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ alignment points (including the two endpoints).  Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment.

Call a "block" the (non-empty) sequence of consecutive intervals between two alignment points.  The left and right endpoint of the interval are automatically alignment points.  If there are $k+1$ distinct alignment points (including these two endpoints), there will be $k$ blocks.

Let $\ell_1,\ell_2,\dots,\ell_n$ be the set of lengths of the first set of subintervals, and $\ell^*_1,\ell^*_2,\dots,\ell^*_{n^*}$ be the lengths of the second set of subintervals.  These are constants provided as input.

Introduce zero-or-one unknowns $x_{i,j}$ (for $1\le i\le n$ and $1 \le j \le k$), with the intent that $x_{i,j}=1$ means that the $i$th subinterval (of length $\ell_i$) from the first partition will end up in the $j$th block.  Similarly, introduce zero-or-one unknowns $x^*_{i,j}$, with the intent that $x^*_{i,j}$ means that the $i$th subinterval (of length $\ell^*_i$) from the second partition will end up in the $j$th block.

Now we get a set of linear inequalities, as follows:


$\sum_i \ell_i x_{i,j} = \sum_i \ell^*_i x^*_{i,j}$, for all $j$.  (This is two ways of representing the length of the $j$th block.)
$\sum_j x_{i,j} = 1$ (each subinterval from the first partition ends up in exactly one block) and $\sum_j x^*_{i,j} = 1$.
$x_{i,j} = 1 \land x_{i+1,j}=0 \implies x_{i+1,j+1} = 1$ (i.e., each block starts where the previous one ended).   This can be expressed as the ILP constraint $x_{i,j} - x_{i+1,j} \le x_{i+1,j+1}$.  Similarly for the $x^*$'s.
$x_{i,j} = 1 \land x_{i'',j} = 1 \land i &lt; i' &lt; i'' \implies x_{i',j}=1$ (i.e., the subintervals in a block are consecutive).  This can be expressed as the ILP constraint $x_{i,j} + x_{i'',j} - 1 \le x_{i',j}$ for all $i,i',i''$ with $i &lt; i' &lt; i''$.  Similarly for the $x^*$'s.
$x_{1,1} = 1$, $x^*_{1,1} = 1$, $x_{n,k}=1$, $x^*_{n^*,k}=1$.


Of course, in the worst case ILP can take exponential time, but ILP solvers are pretty good and often perform well on many real-world problems, so it is probably worth a try.

(You could also try coding this up using a SAT solver, but you'd need to implement arithmetic, so a front-end like STP would probably be a better bet than a plain SAT solver.)