You can use LinearProgramming for this. Let v be a vector of 1s and 0s specifying which sublist is included. Then, the criteria that 3 only appears once is equivalent to:
$$\{1,1,1,0,0\}.v\leq 1$$
That is, only one of the first 3 sublists can be included. With the constraints satisfied, the total number of integers included is just the sum of the lengths of each included sublist. Hence, the objective function is (LinearProgramming returns a minimum):
$$\{-3,-3,-4,-1,-4\}$$
So, a LinearProgramming solution is:
LinearProgramming[
-{3, 3, 4, 1, 4},
{
{1,0,0,0,0}, (* 2 *)
{1,1,1,0,0}, (* 3 *)
{1,1,1,0,1}, (* 4 *)
{0,1,1,0,1}, (* 5 *)
{0,0,1,0,1}, (* 6 *)
{0,0,0,1,1} (* 7 *)
},
Table[{1,-1}, {6}],
0,
Integers
]
LinearProgramming::lpip: Warning: integer linear programming will use a machine-precision approximation of the inputs.
{0, 0, 1, 1, 0}
We can package this up as a function:
disjointMaximum[sets_] := Module[{elems = DeleteDuplicates @ Flatten @ sets, lp},
lp = Quiet[
LinearProgramming[
- Length /@ sets,
Table[Boole @ Map[Not@*FreeQ[k]] @ sets, {k, elems}],
Table[{1, -1}, {Length[elems]}],
0,
Integers
],
LinearProgramming::lpip
];
Pick[sets, lp, 1]
]
For the OP example, we again get:
disjointMaximum[{{2, 3, 4}, {3, 4, 5}, {3, 4, 5, 6}, {7}, {4, 5, 6, 7}}]
{{3, 4, 5, 6}, {7}}