Performing a type of union of two IEnumerable collections

Question

Let's say you have two collections of integers:

IEnumerable<int> col1=new List<int> {2,3,3,5,7,11,11,11,13};
IEnumerable<int> col2=new List<int> {5,7,7,7,11,19};

Now I would like to create a third collection, col3, such that for every distinct element that appears in either col1 or col2, col3 will contain that element with at least as many occurances as the maximum number of occurrences of the element in either col1 or col2, but no more. Let me show the end result, then elaborate further:

   IEnumerable<int> col3=...;

The contents of col3 should be:

{2,3,3,5,7,7,7,11,11,11,13,19}

Another way to describe the contents of col3 as the result of this "pseudo-union" operation is that it should contain enough elements of each value, but no more, such that either of the two original collections could be formed individually (i.e., one at a time, from the entire domain of numbers in col3) by extracting elements from col3.

In case there is still confusion by what I mean when I say, "one at a time", imagine that col1 and col2 are instead collections of different types of marbles, with duplicates. I want to form col3 such that I have the minimum amount of the different types of marbles, so that I can remove enough marbles from col3 to form col1, then put the marbles back into col3, then remove enough marbles to form col2.

I would love it if the answer used LINQ to come up with a single expression that solves the problem, because the two methods I've thought of so far involve:

1. Merging dictionaries which contain histograms (i.e., number of occurences of each different integer).
2. Constructing a dictionary from col1 and then doing a "mark and insert" type operation while processing col2, resulting in a final dictionary with just enough count for each integer to satisfy my criteria.

Update: The input collections are guaranteed to be sorted (i.e., monotonic and non-decreasing) and the resulting collection should be in the same order.

Answer 1

Like this:

var groups1 = col1.ToLookup(e => e);
var groups2 = col2.ToLookup(e => e);

var col3 = col1.Union(col2)
               .SelectMany(e => Enumerable.Repeat(e, 
                   Math.Max(
                            groups1[e].Count(), 
                            groups2[e].Count()
                   )
                ));