Is the following problem in P or in NP?
The problem can be solved in $O(n^2)$:

Denote $A=\{a_1,\ldots,a_n\}, B=\{b_1,\ldots,b_n\}$.
We will build a graph in which every node $(i,j,x)$ will denote which $a$'s and $b$'s we have already executed and $x$ is a bit representing if the last task was $a$.


Construct the product graph $$G_p=(V_p, E_p)$$
$$V_p = A\times B\times \{0,1\}$$
$$E_p = \{((a_i,b_j,x),(a_{i+1},b_j,0))\mid x\in\{0,1\},j\leq i\in[n-1]\}$$
$$ \cup \{((a_i,b_j,x),(a_i,b_{j+1},1)\mid  x\in\{0,1\},j\leq i+1\in[n]\}$$
Assign weights:
$$w(((a_i,b_j,0),(a_{i+1},b_j,0)))=E(a_i,a_{i+1})$$
$$w(((a_i,b_j,1),(a_{i+1},b_j,0)))=E(b_j,a_{i+1})$$
$$w(((a_i,b_j,0),(a_i,b_{j+1},1))) = E(a_i,b_{j+1})$$
$$w(((a_i,b_j,1),(a_i,b_{j+1},1))) = E(b_j,b_{j+1})$$


And now simply find the shortest path with an algorithm of your choice (run time is linear in $|G_p|$, since it is a DAG).