Consider the greedy algorithm that iteratively searches for two distinct pairs of intervals that can be merged, merges them, and repeats until no more merges are possible.
We need to show that this algorithm is optimal.
Notice that, at each point in time during the algorithm, we can associate the generic $i$-th pair $\mathcal{I}_i$ with a set $P_i$ containing all the original pairs that were ultimately merged into $\mathcal{I}_i$.
Similarly, consider an optimal solution $\mathcal{I}^*_1, \mathcal{I}^*_2, \dots, \mathcal{I}^*_\ell$ and define $P^*_1, \dots, P^*_\ell$ as the corresponding sets of original pairs.
Let $k$ be the number of intervals returned by the greedy algorithm.
We want to show that $k \le \ell$ (which implies $k = \ell$).
We start by showing that the final sets induced by an execution of the greedy algorithm must be a refinement of $P^*_1, \dots, P^*_\ell$.
Suppose that this is false and pick the first point in time at which the greedy algorithm merges two pairs $\mathcal{I}_i$ and $\mathcal{I}_j$ associated with sets $P_i$ and $P_j$ where $P_i \subseteq P^*_h$ and $P_j \subseteq P^*_z$ with $h \neq z$.
Since $\mathcal{I}_i$ can be merged with $\mathcal{I}_j$, $\mathcal{I}^*_h$ contains $\mathcal{I}_i$, and $\mathcal{I}^*_z$ contains $I_j$, we must have that $\mathcal{I}^*_h$ can be merged with $\mathcal{I}^*_z$ contradicting the optimality of $\mathcal{I}^*_1, \mathcal{I}^*_2, \dots, \mathcal{I}^*_\ell$.
Suppose now that $k > \ell$. Then there is some set $P^*_h$ that is partitioned into $m \ge 2$ sets $P'_{1}, \dots, P'_{m}$ from $\{P_1, \dots, P_k\}$. Let $\mathcal{I}'_i$ be the pair corresponding to $P'_i$.
The merge operation that resulted in $P^*_h$ can be described as a binary tree $T$ in which each leaf represents a pair in $P^*_h$, every internal node $v$ represents a merged pair $\mathcal{I}(v)$, and the root $r$ represents $\mathcal{I}(r) = \mathcal{I}^*_h$. Let $P(v)$ be the set corresponding to $\mathcal{I}(v)$.
Locate the deepest vertex $v$ in $T$ such that its two children $u$ and $w$ satisfy $P(u) \subseteq P'_i$ and $P(w) \subseteq P'_j$ for $i \neq j$.
We must have that $\mathcal{I}'_i$ contains $\mathcal{I}(u)$ and
$\mathcal{I}'_j$ contains $\mathcal{I}(w)$. Therefore, since $\mathcal{I}(u)$ and $\mathcal{I}(w)$ can be merged into $\mathcal{I}(v)$, the pairs $\mathcal{I}'_i$ and $\mathcal{I}'_j$ can also be merged. This contradicts the stopping condition of our greedy algorithm.
To implement the greedy algorithm efficiently you can first transform the input instance so that two pairs can be merged if and only if their intervals intersect. Then interpret the intervals in a pair as the sides of a rectangle.
Use a data structure $D$ that is able to (i) maintain a dynamic collection of rectangles and (ii) report all rectangles intersecting with a given query rectangle. For example, you can use a dynamic range tree that supports each of the above operations in $O(\mathrm{polylog}\, m)$ amortized time, where $m$ is the number of stored rectangles.
Repeat the following:
- For each input pair $\mathcal{I}$:
- While $D$ contains some pairs (rectangles) that intersect with $\mathcal{I}$.
- Delete all such pairs from $D$ and let $\mathcal{I}$ be the pair obtained by merging $\mathcal{I}$ with all of them.
- Insert $\mathcal{I}$ into $D$.
At the end of the algorithm, the contents of $D$ are exactly the final set of pairs.
To analyze the time complexity of this algorithm notice that each original pair is inserted at most once into $D$ and can be associated to exactly one query to $D$ that does not satisfy the condition of the while loop. Moreover, the number of merged pairs is at most $n-1$, where $n$ is the number of pairs in input. Each merge inserts at most one pair into $D$ and is respondible for one query. The number of pairs deleted from $D$ is upper bounded by the number of insertions. Overall we perform $O(n)$ operations on $D$.
The overall time needed is then $O(n \, \mathrm{polylog} \, n)$.
