Select at least one from each category to minimize union, NP-hard problem?
Nice question! Let us call this problem the minimum label-covering problem.
We will reduce the hitting set problem, a well-known $\mathsf{NP}$-hard problem to the minimum label-covering problem, thus proving it is also $\mathsf{NP}$-hard. Our strategy is simply translating &quot;intersecting the $i$-th set&quot; in the hitting set problem to &quot;labelled with the $i$-th label&quot; in the minimum label-covering problem.
Given $V=\{V_1, V_2,\cdots, V_m\}$, which is a collection of subsets of a finite set $U$ and a number $k$, the hitting set problem is to find the smallest subset of $U$ which intersects (hits) every set in $V$. Let $S$ be the disjoint union of $U$ and $\{l_1,l_2,\cdots, l_m\}$, a set of $m$ labels. Let $C$ be the set of all subsets of $S$ of the form $\{u, l_i\}$ where $u\in V_i$.  Let the label for $\{u, l_i\}$ be $l_i$. Suppose we have solved the minimum label-covering problem for $C$, $S$ and the specified labelling, that is, we have selected at least one set from each category such that their union is minimized. Let $U'$ be the set of all elements of $U$ that are members of the selected sets. It is easy to verify that $U'$ is the smallest subset of $U$ that hits every set in $V$. Our proof is done.
An exercise
Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category, the maximum label-covering problem is to select at most one $c$ from each category such that the size of their union is maximized. Show the maximum label-covering problem is $\mathsf{NP}$-hard.