2 Fixed complexity bounds.

Call the set containing the sets of intervals $S$ and build a graph $G_S$ from $S$ as follows: Each set of intervals $I \in S$ becomes a vertex, and there is an edge between interval set $I$ and interval set $J$ if and only if some interval in $I$ overlaps with some interval in $J$. So for your example, the graph would have three vertices:

$$A = {(1,2),(3,4)}, B = {(1,3)}, C = {(13,14)}$$

And there is an edge from $A$ to $B$ since $(1,2)$ overlaps $(1,3)$.

Now, the number of connected components of $G_S$ gives you the "number of non-pairwise overlapping interval sets" and picking a vertex from each connected component furnishes a solution to your problem.

So back to your example: the connected components are $AB$ and $C$, so you can pick either $A$ and $C$ or $B$ and $C$, as you have said.

Regarding efficiency: the worst-case complexity of building this graph is $O(m^2n)$ O(m^2n^2)$where$m$is the cardinality of$S$and$n$is the maximal cardinality of any interval set$I \in S$. 1 Call the set containing the sets of intervals$S$and build a graph$G_S$from$S$as follows: Each set of intervals$I \in S$becomes a vertex, and there is an edge between interval set$I$and interval set$J$if and only if some interval in$I$overlaps with some interval in$J$. So for your example, the graph would have three vertices: $$A = {(1,2),(3,4)}, B = {(1,3)}, C = {(13,14)}$$ And there is an edge from$A$to$B$since$(1,2)$overlaps$(1,3)$. Now, the number of connected components of$G_S$gives you the "number of non-pairwise overlapping interval sets" and picking a vertex from each connected component furnishes a solution to your problem. So back to your example: the connected components are$AB$and$C$, so you can pick either$A$and$C$or$B$and$C$, as you have said. Regarding efficiency: building this graph is$O(m^2n)$where$m$is the cardinality of$S$and$n$is the maximal cardinality of any interval set$I \in S\$.