Hello Andrei,
This is somewhat OT but I think it's an interesting problem. Consider
the following data:
double[][] a =
[
[ 1, 4, 7, 8 ],
[ 1, 7 ],
[ 1, 7, 8],
[ 4 ],
[ 7 ],
];
We want to compute an n-way union, i.e., efficiently span all elements
in all arrays in a, in sorted order. You can assume that each
individual array in a is sorted. The output of n-way union should be:
auto witness = [
1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8
];
assert(equal(nWayUnion(a), witness[]));
The STL and std.algorithm have set_union that does that for two sets:
for example, set_union(a[0], a[1]) outputs [ 1, 1, 4, 7, 7, 8 ]. But
n-way unions poses additional challenges. What would be a fast
algorithm? (Imagine a could be a very large range of ranges).
Needless to say, nWayUnion is a range :o).
Finally, why would anyone care for something like this?
Andrei
in sudocode
1. build a min heap out of the elements based on the first element of each
array
2. remove the first value from the root of the heap,
3. if empty array, drop it
4. if not empty re-heap
5. goto 2 if anything left
