Suppose, I have a set of sets $S = \{ X_1, \cdots, X_i, \cdots, X_K\}, X_i \subset \mathbb{R}$ and need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. It is rather hard, so I want to prove it's hard. Denote $K(X) = \cup_{I \in X} I$, $E(x) := \sum_{i \in K(X)} |i - \textbf{median}(K(X))|$. And $|.|$ is the absolute value. For simplicy, assume $X_i \cap X_j = \emptyset, \forall X_i, X_j \in S$.

But I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $L^*$ and $R^*$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete.

Can I conclude the original problem is at least NP-complete?